Submission #1073252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073252		Ludissey	Holiday (IOI14_holiday)	C++17	7 / 100	71 ms	65536 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
 

int s=0;
int n;
vector<vector<vector<vector<int>>>> memo;
vector<int> a;

int dp1(int x, int d, bool changedir){
    if(d==0) return 0;
    else if(d<0) return -1e9;
    if(memo[x][d][changedir][0]>-1) return memo[x][d][changedir][0];
    int mx=0;
    int nxt=0;
    int nxtCH=0;
    int nxtCH2=0;
    int nxt2=0;
    if(!changedir){
        if(x>0){
            nxt=dp1(x-1,d-1,false);
            nxt2=dp1(x-1,d-2,false);
        }
        if(x<n-1){
            nxtCH=dp1(x+1,d-1,true);
            nxtCH2=dp1(x+1,d-2,true);
        }
    }else{
        if(x<n-1){
            nxt=dp1(x+1,d-1,true);
            nxt2=dp1(x+1,d-2,true);
        }
    }
    mx=max(mx,nxt);
    if(!changedir) mx=max(mx,nxtCH);

    if(!changedir||x>s){
        if(d==1){
            mx=max(mx,a[x]);
        }else{
            mx=max(mx,a[x]+nxt2);
            if(!changedir) mx=max(mx,a[x]+nxtCH2);
        }
    }
    return memo[x][d][changedir][0]=mx;
}


int dp2(int x, int d, bool changedir){
    if(d==0) return 0;
    else if(d<0) return -1e9;
    if(memo[x][d][changedir][1]>-1) return memo[x][d][changedir][1];
    int mx=0;
    int nxt=0;
    int nxtCH=0;
    int nxtCH2=0;
    int nxt2=0;
    if(!changedir){
        if(x<n-1){
            nxt=dp2(x+1,d-1,false);
            nxt2=dp2(x+1,d-2,false);
        }
        if(x>0){
            nxtCH=dp2(x-1,d-1,true);
            nxtCH2=dp2(x-1,d-2,true);
        }
    }else{
        if(x>0){
            nxt=dp2(x-1,d-1,true);
            nxt2=dp2(x-1,d-2,true);
        }
    }
    mx=max(mx,nxt);
    if(!changedir) mx=max(mx,nxtCH);

    if(!changedir||x<s){
        if(d==1){
            mx=max(mx,a[x]);
        }else{
            mx=max(mx,a[x]+nxt2);
            if(!changedir) mx=max(mx,a[x]+nxtCH2);
        }
    }
    return memo[x][d][changedir][1]=mx;
}


int findMaxAttraction(signed N, signed start, signed d, signed attraction[]) {
    s=start;
    a.resize(N);
    n=sz(a);
    for (int i = 0; i < n; i++) a[i]=attraction[i];
    memo.resize(n,vector<vector<vector<int>>>(d+1,vector<vector<int>>(2,vector<int>(2,-1))));
    int sm=dp1(s,d,0);
    sm=max(sm,dp2(s,d,0));    
    return sm;
}

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