Submission #129518

#	Time	Username	Problem	Language	Result	Execution time	Memory
129518		antimirage	Holiday (IOI14_holiday)	C++14	17 / 100	5095 ms	2264 KiB

holiday

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

using namespace std;


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) {
		priority_queue <int, vector <int>, greater <int> > st;
		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;
			priority_queue <int, vector <int>, greater <int> > st1, st2, st3, st4;

			for (int i = 0; i < x; i++) {
				if (start + i >= n) break;
				
				st1.push( a[start + i] );
				sum += a[start + i];
				int k = x - i;
				
				while (st1.size() > k) {
					sum -= st1.top();
					st1.pop();
				}
				res1 = max(res1, sum);
			}
			sum = 0;
			for (int i = 1; i * 2 <= rem; i++) {
				if (start - i < 0) break;
				
				st2.push( a[start - i] );
				sum += a[start - i];
				int k = rem - i * 2;
				
				while (st2.size() > k) {
					sum -= st2.top();
					st2.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;
				
				st3.push( a[start + i] );
				sum += a[start + i];
				int k = x - i * 2;
				
				while (st3.size() > k) {
					sum -= st3.top();
					st3.pop();
				}
				res1 = max(res1, sum);
			}
			sum = 0;
			
			for (int i = 1; i < rem; i++) {
				if (start - i < 0) break;
				
				st4.push( a[start - i] );
				sum += a[start - i];
				int k = rem - i;
				
				while (st4.size() > k) {
					sum -= st4.top();
					st4.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:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st1.size() > k) {
            ~~~~~~~~~~~^~~
holiday.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st2.size() > k) {
            ~~~~~~~~~~~^~~
holiday.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st3.size() > k) {
            ~~~~~~~~~~~^~~
holiday.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st4.size() > k) {
            ~~~~~~~~~~~^~~

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