| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1312057 | norrawichzzz | Jelly Flavours (IOI20_jelly) | C++20 | 0 ms | 0 KiB |
#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>> od(n);
for (int i=0; i<n; i++) od[i] = {a[i], b[i]};
//sort(od.begin(), od.end());
vector<vector<pair<int,int>>> dp(n+1, vector<pair<int,int>>(y+1));
dp[0][0] = {0, 0};
for (int i=1; i<=n; i++) {
for (int j=y; j>=0; j--) {
dp[i][j] = dp[i-1][j];
int addx = od[i-1].first, addy=od[i-1].second;
if (dp[i-1][j].first + addx <= x) {
dp[i][j].first += addx;
dp[i][j].second++;
}
if (j - addy >= 0) {
if (dp[i-1][j-addy].second + 1 > dp[i][j].second) dp[i][j] = {dp[i-1][j-addy].first, dp[i-1][j-addy].second+1};
else if (dp[i-1][j-addy].second + 1 == dp[i][j].second) dp[i][j].first = min(dp[i][j].first, dp[i-1][j-addy].first);
}
}
}
return dp[n][y].second;
}
/**/
int main() {
int n,x,y;
cin>> n>> x>> y;
vector<int> a(n), b(n);
for (int i=0; i<n; i++) cin>> a[i];
for (int i=0; i<n; i++) cin>> b[i];
cout<< find_maximum_unique(x, y, a, b);
}
