#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2010;
const int maxx=10010;
int dp1[maxn][maxx], dp2[maxn][maxx],a[maxn], b[maxn];
int find_maximum_unique(int x, int y, vector<int> A, vector<int> B){
int n=A.size();
vector<pair<int,int>>process;
for(int i=0;i<n;i++) process.push_back({A[i],B[i]});
sort(process.begin(),process.end());
for(int i=0;i<n;i++){
a[i]=process[i].first; b[i]=process[i].second;
}
for(int i=n-1;i>=0;i--){
for(int j=0;j<=y;j++){
dp2[i][j]=dp2[i+1][j];
if(j>=b[i]) dp2[i][j]=max(dp2[i][j],dp2[i+1][j-b[i]]+1);
}
}
for(int i=0;i<n;i++)
for(int j=0;j<=x;j++) dp1[i][j]=maxx;
dp1[0][0]=b[0]; dp1[0][a[0]]=0;
int resp=0;
if(b[0]<=y) resp=max(resp,1+dp2[1][y-b[0]]);
if(a[0]<=x) resp=max(resp,1+dp2[1][y]);
for(int i=1;i<n;i++){
for(int j=0;j<=x;j++){
dp1[i][j]=dp1[i-1][j]+b[i]; // ele tem q pegar o b[i] tbm
if(j>=a[i]) dp1[i][j]=min(dp1[i][j],dp1[i-1][j-a[i]]);
if(dp1[i][j]<=y) resp=max(resp,i+1+dp2[i+1][y-dp1[i][j]]);
}
}
return resp;
}
# | 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... |