제출 #586553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586553		SeDunion	휴가 (IOI14_holiday)	C++17	0 / 100	56 ms	65536 KiB

holiday

#include"holiday.h"
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;
using ll = long long;

const int N = 3003;
const int D = 2*N + N/2;

ll dp[N][D];

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	ll ans = 0;
	for (int _ = 0 ; _ < 2 ; ++ _) {
		for (int i = 0 ; i < N ; ++ i) for (int j = 0 ; j < D ; ++ j) {
			dp[i][j] = 0;
		}
		for (int i = 0 ; i < n ; ++ i) {
			for (int j = 0 ; j <= d ; ++ j) {
				if (j > 0) dp[i][j] = max(dp[i][j], (ll)attraction[i]);
				if (i > 0 && j > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]); 
				if (i > 0 && j > 1) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + attraction[i]);
				if (j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
			}
		}
		for (int i = start ; i < n ; ++ i) {
			int x = d - (i - start);
			if (x >= 0) ans = max(ans, dp[i][x]);
		}
		reverse(attraction, attraction + n);
		start = n - start - 1;
	}
	return ans;
}

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