| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1169060 | user736482 | Jelly Flavours (IOI20_jelly) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define POT 4194304
#define INF 1000000019
#define INFL 1000000000000000099LL
ll gdzie1[5007],gdzie2[5007];
ll dp1[5007][10007];//kupujac dany pref v1 placac [j] z x, ile placimy z y
int find_maximium_unique(int x,int y,vector<int>a,vector<int>b){
//cout<<"xd"<<flush;
//return 0;
vector<pair<ll,ll>>v1,v2;
for(ll i=0;i<a.size();i++){
v1.pb({a[i],i});
v2.pb({b[i],i});
}
// cout<<"xd"<<flush;
//return 0;
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
for(ll i=0;i<a.size();i++){
gdzie1[v1[i].ss]=i;
gdzie2[v2[i].ss]=i;
}
//cout<<"xd"<<flush;
for(ll i=0;i<10007;i++)dp1[0][i]=0;
//return 0;
for(ll i=1;i<=a.size();i++){
for(ll j=0;j<=x;j++){
dp1[i][j]=dp1[i-1][j]+b[v1[i-1].ss];
if(j>=a[v1[i-1].ss])
dp1[i][j]=min(dp1[i-1][j-a[v1[i-1].ss]],dp1[i][j]);
// cout<<i<<" "<<j<<" "<<dp1[i][j]<<"\n";
// cout<<i-1;
//if(j>=0)
// return 0;
// cout<<"xd"<<flush;
}
}
// cout<<"xd"<<flush;
//return 0;
ll bst=0;
for(ll i=0;i<=a.size();i++){// prefix kupiony z v1
ll iley=y-dp1[i][x];
if(iley<0)
continue;
ll ak=0;
ll akwyn=i;
while(y>=0 && ak<a.size()){
if(gdzie1[v2[ak].ss]<i){
ak++;
continue;
}
akwyn++;
iley-=v2[ak].ff;
if(iley<0)
akwyn--;
ak++;
}
bst=max(bst,akwyn);
}
return bst;
}