Submission #385771

#	Time	Username	Problem	Language	Result	Execution time	Memory
385771		taulant	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	154 ms	153068 KiB

jelly

#include<bits/stdc++.h>
using namespace std;
typedef array<int, 2> pii;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){
 int n = a.size();
 vector<pii> c(n);
 for(int i = 0; i < n; ++i) c[i] = {a[i], b[i]};
 sort(c.begin(), c.end());
 vector<vector<int>> v(n+1, vector<int>(x+1)), w(n+1, vector<int>(y+1));
 // v: buy i cheapest jelly, given money spent in a, find min extra cost in b
 for(int i = 1; i <= n; ++i){
  for(int j = 0; j <= x; ++j){
   v[i][j] = v[i-1][j] + c[i-1][1];
   if(j >= c[i-1][0]) v[i][j] = min(v[i][j], v[i-1][j-c[i-1][0]]);
  }
 }
 // w: buy in b jelly that would be expensive in a, find max jelly
 for(int i = n-1; i >= 0; --i){
  for(int j = 0; j <= y; ++j){
   w[i][j] = w[i+1][j];
   if(j >= c[i][1]) w[i][j] = max(w[i][j], w[i+1][j-c[i][1]]+1);
  }
 }
 int ans = 0;
 for(int i = 0; i <= n; ++i){
  int yy = y - v[i][x];
  if(yy >= 0) ans = max(ans, i + w[i][yy]);
 }
 return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32