Submission #1097710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097710		Alihan_8	Holiday (IOI14_holiday)	C++17	23 / 100	34 ms	6736 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 <int> a(n);
	
	for ( int i = 0; i < n; i++ ) a[i] = attraction[i];
	
	i64 opt = 0, cnt = 0;
	
	multiset <i64> A, B;
	
	for ( int i = 0; i < min(n, d); i++ ){
		B.insert(a[i]);
		
		while ( !B.empty() && (int)A.size() < d - i ){
			auto it = --B.end(); B.erase(it);
			
			A.insert(*it); cnt += *it;
		}
		
		while ( (int)A.size() > d - i ){
			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: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53