# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
434164 | 2021-06-20T16:33:03 Z | TLP39 | Jelly Flavours (IOI20_jelly) | C++14 | 0 ms | 0 KB |
#include "jelly.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int MAX_I=2000000000; int n; pii c[2000]; int ans; int jelly_num[2001][10001]; map<int,int> mp; int min_b[10001]; int qs,cou; int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) { n = a.size(); for(int i=0;i<n;i++) c[i]={a[i],b[i]}; sort(c,c+n); memset(jelly_num,0,sizeof jelly_num); for(int i=n-1;i>=0;i--) { mp[c[i].second]++; qs=0;cou=0; for(auto it=mp.begin();it!=mp.end();it++) { for(int j=0;j<(it->second);j++) { for(int ii=qs;ii<qs+(it->first) && ii<=y;ii++) { jelly_num[n-i][ii]=cou; } qs+=(it->first); cou++; if(qs>y) break; } if(qs>y) break; } for(int j=qs;j<=y;j++) jelly_num[n-i][j]=cou; } for(int i=1;i<=x;i++) min_b[i]=MAX_I; min_b[0]=0; ans=jelly_num[n][y]; for(int i=0;i<n;i++) { for(int j=x;j>=0;j--) { If(j>=c[i].first) min_b[j]=min(min_b[j-c[i].first],min_b[j]+c[i].second); else min_b[j]=min(MAX_I,min_b[j]+c[i].second); if(min_b[j]<=y) { ans=max(ans,jelly_num[n-1-i][y-min_b[j]]); } } } return ans; }