Submission #987699

#	Time	Username	Problem	Language	Result	Execution time	Memory
987699		AdamGS	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	249 ms	313700 KiB

jelly

#include "jelly.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7, MAXX=1e4+7;
ll dppref[LIM][MAXX], dpsuf[LIM][MAXX], n;
pair<ll,ll>T[LIM];
int find_maximum_unique(int x, int y, vector<int>a, vector<int>b) {
  swap(x, y);
  n=a.size();
  rep(i, n) T[i]={a[i], b[i]};
  sort(T, T+n);
  rep(i, n) {
    rep(j, x+1) {
      dppref[i+1][j]=dppref[i][j]+T[i].st;
      if(j>=T[i].nd) dppref[i+1][j]=min(dppref[i+1][j], dppref[i][j-T[i].nd]);
    }
  }
  for(int i=n-1; i>=0; --i) {
    rep(j, x+1) {
      dpsuf[i][j]=dpsuf[i+1][j];
      if(j>=T[i].nd) dpsuf[i][j]=max(dpsuf[i][j], dpsuf[i+1][j-T[i].nd]+1);
    }
  }
  ll ans=0;
  rep(i, n+1) rep(j, x+1) if(dppref[i][j]<=y) ans=max(ans, i+dpsuf[i][x-j]);
  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