#include "jelly.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 2e3+5, MAXY = 1e4+5, INF = 2e9;
int dp1[MAXN][MAXY];//dp1[i][x] := min y gasto pegando todos prefix i e usando até x.
int dp2[MAXN][MAXY];//dp2[i][y] :+ #max que pego do B de sufixo[i..n] gastando ate Y.
int find_maximum_unique(int X, int Y, std::vector<int> a, std::vector<int> b) {
int n = a.size();
vector<pii> tmp;
for(int i = 0; i < n; i++)
tmp.emplace_back(a[i], b[i]);
sort(tmp.begin(), tmp.end());
for(int i = 0; i < n; i++){
a[i] = tmp[i].first;
b[i] = tmp[i].second;
}
for(int i = n; i >= 0; i--){
for(int y = 0; y <= Y; y++){
if(i == n) dp2[i][y] = (b[i]<=y)? 1:0;
dp2[i][y] = max(dp2[i+1][y], (b[i]<=y)? dp2[i+1][y-b[i]]+1:0);
}
}
int ans = 0;
for(int i = 0; i < n; i++){
for(int x = 0; x <= X; x++){
if(!i) dp1[i][x] = min(b[i], (a[i]<=x)? 0:INF);
else dp1[i][x] = min(dp1[i-1][x]+b[i],(a[i]<=x)? dp1[i-1][x-a[i]]:INF);
}
if(dp1[i][X] > Y) break;
if(i == n) ans = i;
ans = max(ans, 1+i+dp2[i+1][Y-dp1[i][X]]);
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |