Submission #129498

#	Time	Username	Problem	Language	Result	Execution time	Memory
129498		antimirage	Holiday (IOI14_holiday)	C++14	30 / 100	5079 ms	5368 KiB

holiday

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

using namespace std;

multiset <int> st;

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.insert(a[i]);
			sum += a[i];
			int k = d - i;
			while (st.size() > k) {
				sum -= *st.begin();
				st.erase(st.begin());
			}
			ans = max(ans, sum);
		}
	} else {
		
		for (int x = 0; x <= d; x++) {
			
			long long res1 = 0, res2 = 0;
			
			st.clear();
			sum = 0;
			int rem = d - x;
			
			for (int i = 0; i < x; i++) {
				if (start + i >= n) break;
				
				st.insert( a[start + i] );
				sum += a[start + i];
				int k = x - i;
				
				while (st.size() > k) {
					sum -= *st.begin();
					st.erase(st.begin());
				}
				res1 = max(res1, sum);
			}
			st.clear();
			sum = 0;
			//cout << start << endl;
			for (int i = 1; i * 2 <= rem; i++) {
				if (start - i < 0) break;
				
				st.insert( a[start - i] );
				sum += a[start - i];
				int k = rem - i * 2;
				
				while (st.size() > k) {
					sum -= *st.begin();
					st.erase(st.begin());
				}
				res2 = max(res2, sum);
			}
			ans = max(ans, res1 + res2);
		
			//**   		bla bla bla 	**/
			res1 = -1e18, res2 = -1e18;
			
			st.clear();
			sum = 0;
			
			for (int i = 0; i * 2 <= x; i++) {
				if (start + i >= n) break;
				
				st.insert( a[start + i] );
				sum += a[start + i];
				int k = x - i * 2;
				
				while (st.size() > k) {
					sum -= *st.begin();
					st.erase(st.begin());
				}
				res1 = max(res1, sum);
			}
			st.clear();
			sum = 0;
			
			for (int i = 1; i < rem; i++) {
				if (start - i < 0) break;
				
				st.insert( a[start - i] );
				sum += a[start - i];
				int k = rem - i;
				
				while (st.size() > k) {
					sum -= *st.begin();
					st.erase(st.begin());
				}
				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:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (st.size() > k) {
           ~~~~~~~~~~^~~
holiday.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() > k) {
            ~~~~~~~~~~^~~
holiday.cpp:57: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:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() > k) {
            ~~~~~~~~~~^~~

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