제출 #1027744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027744		MarwenElarbi	휴가 (IOI14_holiday)	C++17	0 / 100	58 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[n][d+1];
    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]+attraction[i],dp[i][j]);    
            }
            if(i){
                dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]);
            }
            if(start-i+j<d&&start<n-1){
                dp[start+1][j+start-i]=max(dp[i][j],dp[start+1][j+start-i]);
            }
            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]+attraction[i]);
            }
            if(i<n-1){
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
            }
            ans=max(ans,dp[i][j]);
        }
    }
    return ans;
}



//https://www.youtube.com/playlist?list=PLg_Krngrs0eC_1vn0dTjyPZMkwBOcVsgH

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