Submission #298072

#	Time	Username	Problem	Language	Result	Execution time	Memory
298072		mieszko11b	Holiday (IOI14_holiday)	C++14	47 / 100	5028 ms	6016 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	ll res = 0;
	
	vector<int> a(n);
	for(int i = 0 ; i < n ; i++)
		a[i] = attraction[i];
		
	for(int t = 0 ; t < 2 ; t++) {
		for(int i = start ; i >= 0 ; i--) {
			ll sum = 0;
			multiset<int> S;
			int d2 = d - (start - i);
			for(int j = i ; j < n ; j++) {
				S.insert(a[j]);
				sum += a[j];
				
				//~ cout << i << " " << j << " " << d2 - (j - i ) << endl;
				while(!S.empty() && (int)S.size() > d2 - (j - i)) {
					auto it = S.begin();
					sum -= *it;
					S.erase(it);
				}
				
				//~ cout << sum << " " << S.size() << " " << d2 - (j - i ) << endl;
				res = max(res, sum);
			}
		}
	
		if(n > 3000)
			break;
	
		reverse(a.begin(), a.end());
		start = n - start - 1;
	}
	
    return res;
}

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