| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 434092 | krist7599555 | Jelly Flavours (IOI20_jelly) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <cassert>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
typedef std::vector<int> Vec;
#define rep(i,a,b) for(auto i = a; i != b; ++i)
auto ckmax = [](auto& a, const auto& b) { return b>a?a=b,1:0; };
auto ckmin = [](auto& a, const auto& b) { return b<a?a=b,1:0; };
const int MN = 2e3+10;
const int MV = 1e4+10;
struct st
{
public:
int v, bv;
st inc() {return {v+1, bv};}
void buy(int cost) {++v, bv-=cost;}
bool operator > (const st& o) const {return v > o.v || !(o.v > v) && bv > o.bv;}
} dp[MV];
int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b)
{
int N = a.size();
std::vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int u, int v){return b[u]<b[v];});
for(int i=0;i<=x;++i)
dp[i]={0,y};
for(int i=0;i<N;++i)
{
int k=ord[i];
for(int j=0;j<=x;++j)
{
if(dp[j].bv >= b[k]) dp[j].buy(b[k]);
if(j+a[k]<=x && dp[j+a[k]].inc() > dp[j]) dp[j] = dp[j+a[k]].inc();
}
}
return dp[0].v;
}
inline int input() {
int i; std::cin >> i; return i;
}
int main() {
assert(4 == find_maximum_unique(6, 12, Vec({5, 1, 5, 6, 3}), Vec({3, 5, 4, 6, 7})));
// puts("pass");
using namespace std;
cin.sync_with_stdio(0);
int n = input();
int x = input();
int y = input();
std::vector<int> xn(n);
std::vector<int> yn(n);
rep(i, 0, n) xn[i] = input();
rep(i, 0, n) yn[i] = input();
cout << find_maximum_unique(x, y, xn, yn);
}