Submission #49000

#	Time	Username	Problem	Language	Result	Execution time	Memory
49000		Namnamseo	Holiday (IOI14_holiday)	C++17	47 / 100	397 ms	5400 KiB

holiday

#include"holiday.h"
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;

int dp[3010][3010]; 

ll work1(int n,int S,int d,int a[]){
	ll ans=0;
	for(int i=S; 0<=i; --i){
		priority_queue<int> pq;
		ll sum=0; 
		for(int j=i; j<n; ++j){
			int can_use = d-(S-i)-(j-i);
			if(can_use < 0) continue;
			pq.push(-a[j]); sum += a[j];
			while((int) pq.size() > can_use){
				sum += pq.top(); pq.pop();
			}
			ans = max(ans, sum);
		}
	}
	for(int i=S; i<n; ++i){
		priority_queue<int> pq;
		ll sum = 0;
		for(int j=i; 0<=j; --j){
			int can_use = d-(i-S)-(i-j);
			if(can_use < 0) continue;
			pq.push(-a[j]); sum += a[j];
			while((int) pq.size() > can_use){
				sum += pq.top(); pq.pop();
			}
			ans = max(ans, sum);
		}
	}
	return ans;
}

priority_queue<int,vector<int>,greater<int>> pq;
ll work2(int n,int d,int a[]){
	ll ans=0, sum=0;
	while(pq.size()) pq.pop();
	for(int i=0; i<n; ++i){
		int usable = d-i;
		pq.push(a[i]); sum += a[i];
		while((int)pq.size() > usable){
			sum -= pq.top(); pq.pop();
		}
		ans = max(ans, sum);
	}
	return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(n <= 3000){
    	return work1(n, start, d, attraction);
	} else {
		return work2(n, d, attraction);
	}
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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