Submission #1027870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027870		MarwenElarbi	Holiday (IOI14_holiday)	C++17	0 / 100	50 ms	65536 KiB

holiday

// Sample grader
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define pb push_back
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
    long long dp[3000][7500];
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= d; ++j)
        {
            dp[i][j]=-1e18;
        }
    }
    dp[start][0]=0;
    long long ans=0;
    for (int i = start; i >= 0; --i)
    {
        for (int j = d; j >= 0; --j)
        {
            if(j){
                dp[i][j]=max(dp[i][j-1]+1ll*attraction[i],dp[i][j]);    
            }
            if(i&&j<d){
                dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]);
            }
            if(start-i+j+1<=d&&start<n-1){
                dp[start+1][j+start-i+1]=max(dp[i][j],dp[start+1][j+start-i+1]);
            }
            ans=max(ans,dp[i][j]);
        }
    }
    for (int i = start+1; i < n; ++i)
    {
        for (int j = d; j >= 0; --j)
        {
            if(j){
                dp[i][j]=max(dp[i][j],dp[i][j-1]+1ll*attraction[i]);
            }
            if(i<n-1&&j<d){
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
            }
            ans=max(ans,dp[i][j]);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= d; ++j)
        {
            dp[i][j]=-1e18;
        }
    }
    dp[start][0]=0;
    for (int i = start; i < n; ++i)
    {
        for (int j = d; j >= 0; --j)
        {
            if(j){
                dp[i][j]=max(dp[i][j-1]+1ll*attraction[i],dp[i][j]);    
            }
            if(i<n-1&&j<d){
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
            }
            if(i-start+j+1<=d&&start>0){
                //cout <<i<<" "<<j<<" "<<j-start+i+1<<" "<<dp[i][j]<<endl;
                dp[start-1][j-start+i+1]=max(dp[i][j],dp[start-1][j-start+i+1]);
            }
            ans=max(ans,dp[i][j]);
        }
    }
    for (int i = start-1; i >= 0; --i)
    {
        for (int j = d; j >= 0; --j)
        {
            if(j){
                dp[i][j]=max(dp[i][j],dp[i][j-1]+attraction[i]);
            }
            if(i&&j<d){
                dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]);
            }
            ans=max(ans,dp[i][j]);
        }
    }
    return ans;
}

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