# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1264271 | DeltaStruct | Jelly Flavours (IOI20_jelly) | C++20 | 0 ms | 0 KiB |
#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
int find_maximum_unique(int x,int y,vector<int>& A,vector<int>& B){
int n = A.size(); vector<pair<int,int>> C; for (int i(0);i < n;++i) C.emplace_back(A[i],B[i]);
sort(C.begin(),C.end()); vector dp0(n+1,vector<int>(y+1)),dp1(n+1,vector<int>(y+1));
for (int i(0);i < n;++i){
dp0[i+1] = dp0[i];
for (int k(0);k+C[i].second <= y;++k) dp0[i+1][k+C[i].second] = max(dp0[i+1][k+C[i].second],dp0[i][k]+C[i].first);
}
for (int i(n-1);i > -1;--i){
dp1[i] = dp1[i+1];
for (int k(0);k+C[i].second <= y;++k) dp1[i][k+C[i].second] = max(dp1[i][k+C[i].second],dp1[i+1][k]+1);
}
int r = 0,s = 0;
for (int i(0);i <= n;++i){
for (int k(0);k <= y;++k) if (s-dp0[i][k]<=x) r = max(r,i+dp1[i][y-k]);
if (i!=n) s += C[i].first;
}
return r;
}