Submission #1143483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143483		adriines06	Holiday (IOI14_holiday)	C++20	0 / 100	66 ms	131072 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

long long int findMaxAttraction(int n, int s, int d, int attraction[]) {

    vector<ll> v(attraction, attraction + n);
    vector<ll> a1,a2;
    for(ll &x: v) cin>>x;
    for(ll i=s;i>=0;i--){
        a1.push_back(v[i]);
    }
    for(ll i=s;i<n;i++){
        a2.push_back(v[i]);
    }
    ll l=4*n;
    vector<vector<ll>>dp1(a1.size(),vector<ll>(l,-1));
    vector<vector<bool>>nd1(a1.size(),vector<bool>(l,0));
    dp1[0][0]=0;
    dp1[0][1]=v[s];
    nd1[0][0]=0;
    nd1[0][1]=1;
    ll b=0,f=1;
    for(ll i=1;i<a1.size();i++){
        for(ll j=b;j<=f;j++){
            if(dp1[i-1][j]+a1[i]>dp1[i][j+2]){
                nd1[i][j+2]=nd1[i-1][j];
            }
            if(dp1[i-1][j]>dp1[i][j+1]){
                nd1[i][j+1]=nd1[i-1][j];
            }

            dp1[i][j+2]=max(dp1[i][j+2], dp1[i-1][j]+a1[i]);
            dp1[i][j+1]=max(dp1[i][j+1], dp1[i-1][j]);
        }
        b=b+1;
        f=f+2;
    }

    vector<ll>k1(f+1,-1);
    vector<ll>v1(f+1,-1);
    vector<bool>n1(f+1,false);
    b=1,f=3;
    k1[0]=0, k1[1]=v[s];
    v1[0]=0, v1[1]=0;
    n1[0]=0, n1[1]=1;
    for(ll i=1;i<a1.size();i++){
        for(ll j=b;j<=f;j++){
            if(dp1[i][j]>k1[j]){
                v1[j]=i;
                if(nd1[i][j]){
                    n1[j]=1;
                }
            }
            k1[j]=max(k1[j],dp1[i][j]);
        }
        b=b+1;
        f=f+2;
    }
    
    vector<vector<ll>>dp2(a2.size(),vector<ll>(l,-1));
    vector<vector<bool>>nd2(a2.size(),vector<bool>(l,0));
    dp2[0][0]=0;
    dp2[0][1]=v[s];
    nd2[0][0]=0;
    nd2[0][1]=1;
    b=0,f=1;
    for(ll i=1;i<a2.size();i++){
        for(ll j=b;j<=f;j++){
            if(dp2[i-1][j]+a2[i]>dp2[i][j+2]){
                nd2[i][j+2]=nd2[i-1][j];
            }
            if(dp2[i-1][j]>dp2[i][j+1]){
                nd2[i][j+1]=nd2[i-1][j];  
            }
            dp2[i][j+2]=max(dp2[i][j+2], dp2[i-1][j]+a2[i]);
            dp2[i][j+1]=max(dp2[i][j+1], dp2[i-1][j]);
        }
        b=b+1;
        f=f+2;
    }

    vector<ll>k2(f+1,-1);
    vector<ll>v2(f+1,-1);
    vector<bool>n2(f+1,false);
    b=1,f=3;
    k2[0]=0, k2[1]=v[s];
    v2[0]=0, v2[1]=0;
    n2[0]=0, n2[1]=1;
    for(ll i=1;i<a2.size();i++){
        for(ll j=b;j<=f;j++){
            if(dp2[i][j]>k2[j]){
                v2[j]=i;
                if(nd2[i][j]){
                    n2[j]=1;
                }
            }
            k2[j]=max(k2[j],dp2[i][j]);
        }
        b=b+1;
        f=f+2;
    }


    ll ans=0;
    ll av,bv,vf;
    for(ll i=0;i<k1.size();i++){
        if(i>d) break;
        for(ll j=0;j<k2.size();j++){
            ll r=k1[i]+k2[j];
            if(n1[i]&&n2[j]){
                r-=v[s];
            }
            ll v=min(v1[i],v2[j]);
            if(i+j+v<=d){
                ans=max(ans,r);
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53