제출 #1075355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1075355		mindiyak	휴가 (IOI14_holiday)	C++14	0 / 100	5060 ms	37332 KiB

holiday

#include"holiday.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
#define ll long long 

ll ans = 0;
int D,N;
vector<int> att;

void dfs(int pos,int len,ll cnt,set<int> visited){
    if(len > D)return;
    if(len == D){
        // cerr << cnt << " | ";
        // for(int a:visited)cerr << a;
        // cerr << endl;
        ans = max(ans,cnt);
        return;
    }
    if(pos > 0){
        dfs(pos-1,len+1,cnt,visited);
    }
    if(pos < N-1){
        dfs(pos+1,len+1,cnt,visited);
    }
    if(visited.count(pos) == 0){
        visited.insert(pos);
        cnt += att[pos];
        if(len+1 == D){
            // cerr << cnt << " | ";
            // for(int a:visited)cerr << a;
            // cerr << endl;
            ans = max(ans,cnt);
            return;
        }
        if(pos > 0){
            dfs(pos-1,len+2,cnt,visited);
        }
        if(pos < N-1){
            dfs(pos+1,len+2,cnt,visited);
        }
        cnt -= att[pos];
        visited.erase(pos);
    }
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    N = n;
    D = d;
    for(int i=0;i<n;i++)att.push_back(attraction[i]);

    set<int> visited;
    dfs(start,0,0,visited);

    return ans;
}

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