Submission #543814

#	Time	Username	Problem	Language	Result	Execution time	Memory
543814		Sho10	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	255 ms	313752 KiB

jelly

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#include "jelly.h"
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
pair<ll,ll>a[2005];
ll dp1[2005][10005],dp2[2005][10005];
int find_maximum_unique(int x,int y,vector<int>A,vector<int>B){
ll n=A.size();
for(ll i=1;i<=n;i++)
{
    a[i].f=A[i-1];
    a[i].s=B[i-1];
}
sort(a+1,a+n+1);
for(ll i=0;i<=n;i++)
{
    for(ll j=0;j<=x;j++){
        dp1[i][j]=LINF;
    }
    for(ll j=0;j<=y;j++)
    {
        dp2[i][j]=LINF;
    }
}
for(ll j=0;j<=y;j++)
{
    dp2[n][j]=0;
}
dp1[0][0]=0;
for(ll i=1;i<=n;i++)
{
    for(ll j=0;j<=x;j++)
    {
        ll val=j-a[i].f;
        if(val>=0){
            dp1[i][j]=min(dp1[i][j],dp1[i-1][val]);
        }
        if(dp1[i-1][j]!=LINF){
            ll nr=dp1[i-1][j]+a[i].s;
            if(nr<=y){
                dp1[i][j]=min(dp1[i][j],nr);
            }
        }
    }
}
for(ll i=n-1;i>=0;i--)
{
    for(ll j=0;j<=y;j++)
    {
        dp2[i][j]=dp2[i+1][j];
        ll val=j-a[i+1].s;
        if(val>=0){
            dp2[i][j]=max(dp2[i][j],dp2[i+1][val]+1);
        }
    }
}
ll ans=0;
for(ll i=0;i<=n;i++)
{
    for(ll j=0;j<=x;j++)
    {
        ll nr=dp1[i][j];
        if(nr!=LINF){
            ans=max(ans,i+dp2[i][y-nr]);
        }
    }
}
int res=ans;
return res;
}
/*
int32_t main(){
CODE_START;
#ifdef LOCAL
    ifstream cin("input.txt");
#endif
*/

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