제출 #385948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385948		alireza_kaviani	휴가 (IOI14_holiday)	C++11	47 / 100	29 ms	1384 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;

typedef long long ll;

const int MAXN = 8000;

ll dp[MAXN] , ans[MAXN][2][2];
priority_queue<int , vector<int> , greater<int>> pq;

long long int findMaxAttraction(int n, int start, int d, int A[]) {
	if(start == 0){
		ll ans = 0 , sum = 0;
		for(int i = 0 ; i < n ; i++){
			sum += A[i];
			pq.push(A[i]);
			while(pq.size() > d - i){
				sum -= pq.top(); pq.pop();
			}
			ans = max(ans , sum);
		}
		return ans;
	}
	for(int i = start ; i < n ; i++){
		for(int j = n ; j >= 1 ; j--){
			dp[j] = max(dp[j] , dp[j - 1] + A[i]);
		}
		for(int j = 0 ; j <= n ; j++){
			ans[j + (i - start)][0][0] = max(ans[j + (i - start)][0][0] , dp[j]);
			ans[j + (i - start) * 2][0][1] = max(ans[j + (i - start) * 2][0][1] , dp[j]);
		}
	}
	fill(dp , dp + MAXN , 0);
	for(int i = start - 1 ; i >= 0 ; i--){
		for(int j = n ; j >= 1 ; j--){
			dp[j] = max(dp[j] , dp[j - 1] + A[i]);
		}
		for(int j = 0 ; j <= n ; j++){
			ans[j + (start - i)][1][0] = max(ans[j + (start - i)][1][0] , dp[j]);
			ans[j + (start - i) * 2][1][1] = max(ans[j + (start - i) * 2][1][1] , dp[j]);
		}
	}
	for(int i = 1 ; i < MAXN ; i++){
		for(int j = 0 ; j < 2 ; j++){
			for(int k = 0 ; k < 2 ; k++){
				ans[i][j][k] = max(ans[i][j][k] , ans[i - 1][j][k]);
			}
		}
	}
	ll res = 0;
	for(int i = 0 ; i <= d ; i++){
		res = max(res , ans[i][0][0] + ans[d - i][1][1]);
		res = max(res , ans[i][0][1] + ans[d - i][1][0]);
	}
	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:18:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |    while(pq.size() > d - i){
      |          ~~~~~~~~~~^~~~~~~

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