Submission #1097714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097714		Alihan_8	Holiday (IOI14_holiday)	C++17	30 / 100	5059 ms	7004 KiB

holiday

#include"holiday.h"

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

template <class F, class S>
bool chmax(F &u, const S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

long long int findMaxAttraction(int n, int s, int d, int attraction[]) {
	vector <i64> a(n);
	
	for ( int i = 0; i < n; i++ ) a[i] = attraction[i];
	
	i64 opt = 0;
	
	for ( int l = 0; l <= s; l++ ){
		multiset <i64> B, A;
		
		for ( int i = l; i < s; i++ ) B.insert(a[i]);
		
		i64 cnt = 0;
		
		for ( int j = s; j < n; j++ ){
			int step = j - l + min(s - l, j - s);
			
			if ( step > d ) break;
			
			B.insert(a[j]);
			
			while ( !B.empty() && (int)A.size() + step < d ){
				auto it = --B.end(); B.erase(it);
				
				A.insert(*it); cnt += *it;
			}
			
			while ( (int)A.size() + step > d ){
				auto it = A.begin(); A.erase(it);
				
				B.insert(*it); cnt -= *it;
			}
			
			if ( !A.empty() && !B.empty() ){
				while ( *A.begin() < *B.rbegin() ){
					auto x = A.begin(); A.erase(x);
					auto y = --B.end(); B.erase(y);
					
					cnt += *y - *x;
					
					A.insert(*y), B.insert(*x);
				}
			}
			
			chmax(opt, cnt);
		}
	}
	
	return opt;
}

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