oj.uz

답안 #763718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763718 2023-06-22T17:06:31 Z a_aguilo 휴가 (IOI14_holiday) C++14
0 / 100
 35 ms 65536 KB 
#include<bits/stdc++.h>
#include"holiday.h"


using namespace std;

//vector<int> values;
vector<vector<long long int>> dp;
int N, D, START;


long long solveLeft(int city, int day, int attraction[]){
	if(city < 0) return 0;
	if(day <= 0) return 0;
	if(dp[city][day] != -1) return dp[city][day];
	dp[city][day] = max(solveLeft(city-1, day-1, attraction), solveLeft(city-1, day-2, attraction) + attraction[city]);
	return dp[city][day];
}

long long solveRight(int city, int day, int attraction[]){
	if(city >= N) return 0;
	if(day <= 0) return 0;
	if (dp[city][day] != -1) return dp[city][day];
	dp[city][day] = max(attraction[city] + solveLeft(START-1, day - (city - START + 1) - 1, attraction), max(attraction[city] + solveRight(city+1, day-2, attraction), max(solveRight(city+1, day-1, attraction), solveLeft(START-1, day - (city - START + 1) - 1, attraction))));
	return dp[city][day];
}


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    dp = vector<vector<long long int>>(n, vector<long long int>(d,  -1));
    N = n; D = d; START = start;
    /*
    for(int i = 0; i < n; ++i) values[i] = attraction[i];
    */
    return solveRight(start, d, attraction);
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 35 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -