Submission #1169076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169076		user736482	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	86 ms	157000 KiB

jelly

    #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_maximum_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;
    }

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