Submission #962906

#	Time	Username	Problem	Language	Result	Execution time	Memory
962906		hirayuu_oj	Jelly Flavours (IOI20_jelly)	C++17	35 / 100	47 ms	860 KiB

jelly

#include "jelly.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
    int n = a.size();
    n++;
    vector<pair<int,int>> jelly(n);
    rep(i,n){
        jelly[i]={a[i],b[i]};
    }
    jelly[n-1]={x+1,y+1};
    sort(all(jelly));
    vector<int> dp(x+1,y);
    int ans=0;
    multiset<int> aft;
    rep(i,n){
        aft.insert(jelly[i].second);
    }
    rep(i,n+1){
        if(dp[0]<0)break;
        int money=0;
        int now=i;
        ans=max(ans,now);
        for(int j:aft){
            if(money+j<dp[0]){
                money+=j;
                now++;
                ans=max(ans,now);
            }
        }
        aft.erase(aft.find(jelly[i].second));
        if(i==n)break;
        vector<int> ndp(x+1,-1);
        rep(j,x+1){
            ndp[j]=max(ndp[j],dp[j]-jelly[i].second);
            if(j-jelly[i].first>=0){
                ndp[j-jelly[i].first]=max(ndp[j-jelly[i].first],dp[j]);
            }
        }
        swap(dp,ndp);
    }
    return ans;
}

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