oj.uz

Submission #543812

# Submission time Handle Problem Language Result Execution time Memory
543812 2022-03-31T12:25:56 Z Sho10 Jelly Flavours (IOI20_jelly) C++17
0 / 100
 195 ms 310296 KB 
#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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 444 KB 1st lines differ - on the 1st token, expected: '7', found: '8'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 444 KB 1st lines differ - on the 1st token, expected: '7', found: '8'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42456 KB Output is correct
2 Incorrect 39 ms 56936 KB 1st lines differ - on the 1st token, expected: '691', found: '692'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 178620 KB Output is correct
2 Correct 190 ms 305980 KB Output is correct
3 Correct 175 ms 304816 KB Output is correct
4 Correct 189 ms 298996 KB Output is correct
5 Correct 195 ms 310296 KB Output is correct
6 Correct 173 ms 298748 KB Output is correct
7 Correct 175 ms 304352 KB Output is correct
8 Correct 171 ms 300172 KB Output is correct
9 Correct 182 ms 293280 KB Output is correct
10 Correct 188 ms 303588 KB Output is correct
11 Correct 88 ms 169624 KB Output is correct
12 Incorrect 8 ms 16084 KB 1st lines differ - on the 1st token, expected: '0', found: '2'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 174284 KB Output is correct
2 Incorrect 177 ms 294248 KB 1st lines differ - on the 1st token, expected: '99', found: '100'
3 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 444 KB 1st lines differ - on the 1st token, expected: '7', found: '8'
3 Halted 0 ms 0 KB -