Wants and Needs
Time limit: 1 second
Memory limit: 256 megabytes
You are at the shop browsing items. On your checklist, there are \(N\) distinct items. For the \(i_{th}\) item, you need to purchase \(A_i\) pieces but you want to purchase \(B_i\) pieces such that \(B_i \geq A_i\).
When you purchase a piece that you need you gain 1 satisfaction point, but when you purchase a piece that you want you gain 2 points. For example, suppose \(A_i = 3\) and \(B_i = 5\), the first 3 times you purchase a piece of type \(i\), you will gain 1 point, but the \(4_{th}\) and \(5_{th}\) pieces will reward 2 points each. Everything more than \(B_i\) will not reward anything.
What is the minimum number of pieces you need to purchase to gain at least \(K\) satisfaction?
It is guaranteed that you can get at least \(K\) satisfaction.
Input
The first line contains \(N\) and \(K\). \((1 \leq N, K \leq 5000)\)
The next \(N\) lines contains \(A_i\) and \(B_i\). \((0 \leq A_i \leq B_i \leq 10^6)\)
Output
Print the minimum number of pieces needed to get at least \(K\) satisfaction.
Scoring
| Group | Constraints | Points |
|---|---|---|
| \(1\) | \(B_i - A_i \geq K\) | \(20\) |
| \(2\) | \(A_1 = A_2 = ... = A_N\) | \(20\) |
| \(3\) | \(B_1 = B_2 = ... = B_N\) | \(20\) |
| \(4\) | \(K \leq 100\) | \(20\) |
| \(5\) | — | \(20\) |
Example
Input
3 5
3 4
2 3
2 4
Output
4
Solution
The first \(A_i\) pieces of item \(i\) give one point each. Buying all of them unlocks up to \(C_i=B_i-A_i\) pieces worth two points each.
Use knapsack DP. Let dp[c] be the minimum number of one-point pieces needed to unlock at least c two-point pieces. Capacities greater than \(K\) are equivalent, so cap them at \(K\).
For every reachable capacity, try using as many unlocked two-point pieces as needed. Any remaining points can be obtained from unused one-point pieces.
The complexity is \(O(NK)\) time and \(O(K)\) memory.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n), bonus(n);
long long totalBase = 0;
for (int i = 0; i < n; i++) {
int b;
cin >> a[i] >> b;
bonus[i] = min(k, b - a[i]);
totalBase += a[i];
}
const long long INF = (1LL << 60);
vector<long long> dp(k + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int c = k; c >= 0; c--) {
if (dp[c] == INF) continue;
int next = min(k, c + bonus[i]);
dp[next] = min(dp[next], dp[c] + a[i]);
}
}
long long answer = INF;
for (int capacity = 0; capacity <= k; capacity++) {
long long base = dp[capacity];
if (base == INF) continue;
long long use = 0;
if (base < k) {
use = min<long long>(capacity, (k - base + 1) / 2);
}
long long score = base + 2 * use;
long long extraBase = max(0LL, k - score);
if (extraBase <= totalBase - base) {
answer = min(answer, base + use + extraBase);
}
}
cout << answer << '\n';
}