Submission #129517

#	Time	Username	Problem	Language	Result	Execution time	Memory
129517		antimirage	Holiday (IOI14_holiday)	C++14	0 / 100	5046 ms	1400 KiB

holiday

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

using namespace std;

priority_queue <int, vector <int>, greater <int> > st;

inline long long max (long long a, long long b) {
	return a < b ? b : a;
}

long long int findMaxAttraction(int n, int start, int d, int a[]) {
    
    long long ans = 0, sum = 0;
    
    if (start == 0) {
		for (int i = 0; i < n; i++) {
			if (i >= d) break;
			st.push(a[i]);
			sum += a[i];
			int k = d - i;
			while (st.top() > k) {
				sum -= st.top();
				st.pop();
			}
			ans = max(ans, sum);
		}
	} else {
		
		for (int x = 0; x <= d; x++) {
			
			long long res1 = 0, res2 = 0;
			
			sum = 0;
			int rem = d - x;
			
			for (int i = 0; i < x; i++) {
				if (start + i >= n) break;
				
				st.push( a[start + i] );
				sum += a[start + i];
				int k = x - i;
				
				while (st.size() > k) {
					sum -= st.top();
					st.pop();
				}
				res1 = max(res1, sum);
			}
			sum = 0;
			for (int i = 1; i * 2 <= rem; i++) {
				if (start - i < 0) break;
				
				st.push( a[start - i] );
				sum += a[start - i];
				int k = rem - i * 2;
				
				while (st.size() > k) {
					sum -= st.top();
					st.pop();
				}
				res2 = max(res2, sum);
			}
			ans = max(ans, res1 + res2);
		
			res1 = 0, res2 = 0;
			
			sum = 0;
			
			for (int i = 0; i * 2 <= x; i++) {
				if (start + i >= n) break;
				
				st.push( a[start + i] );
				sum += a[start + i];
				int k = x - i * 2;
				
				while (st.size() > k) {
					sum -= st.top();
					st.pop();
				}
				res1 = max(res1, sum);
			}
			sum = 0;
			
			for (int i = 1; i < rem; i++) {
				if (start - i < 0) break;
				
				st.push( a[start - i] );
				sum += a[start - i];
				int k = rem - i;
				
				while (st.size() > k) {
					sum -= st.top();
					st.pop();
				}
				res2 = max(res2, sum);
			}
			ans = max(ans, res1 + res2);
		}
	}
    return ans;
}
/**
5 2 7
10 2 20 30 1
**/

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() > k) {
            ~~~~~~~~~~^~~
holiday.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() > k) {
            ~~~~~~~~~~^~~
holiday.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() > k) {
            ~~~~~~~~~~^~~
holiday.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() > k) {
            ~~~~~~~~~~^~~

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