제출 #1073254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1073254		Ludissey	휴가 (IOI14_holiday)	C++17	7 / 100	666 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<map<int,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][changedir][0].find(d)!=memo[x][changedir][0].end()) return memo[x][changedir][0][d];
    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][changedir][0][d]=mx;
}


int dp2(int x, int d, bool changedir){
    if(d==0) return 0;
    else if(d<0) return -1e9;
    if(memo[x][changedir][1].find(d)!=memo[x][changedir][1].end()) return memo[x][changedir][1][d];
    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][changedir][1][d]=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<map<int,int>>>(2,vector<map<int,int>>(2)));
    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