Submission #243305

#	Time	Username	Problem	Language	Result	Execution time	Memory
243305		rqi	Holiday (IOI14_holiday)	C++14	30 / 100	5057 ms	7916 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define ins insert
#define pb push_back

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 

const int mx = 100005;
const int DIFF = 20;
int n;
int S;
int d;
vl w;

void reversedir(){
	S = n-1-S;
	reverse(all(w));
}

ll solvefixedlengthdirection(int len){ //going left to right
	int days = d-len;
	set<pair<ll, int>> taken;
	set<pair<ll, int>> couldtake;
	int lastr = -5; //last r that is still in taken or couldtake
	int lastl = -5; //last l that was added
	ll ans = 0;
	ll cursum = 0; //sum of everything inside of taken

	for(int i = S; i >= 0; i--){
		int curr = (days-(S-i))+i;
		ckmin(curr, n-1);
		/*if(len == 3){
			cout << i << " " << curr << "\n";
		}*/
		if(curr-i+1 < len) continue; //should continue forever at the end, continue until relevant in the beginning

		if(lastr == -5){ //first interval
			for(int j = i; j <= curr; j++){
				couldtake.ins(mp(w[j], j));
			}
			lastl = i;
			lastr = curr;

			while(sz(taken) < len){
				assert(sz(couldtake) > 0);
				pair<ll, int> good = *(prev(couldtake.end()));
				//put the best value into taken
				couldtake.erase(good);
				taken.ins(good);
				cursum+=good.f;
			}
		}
		else{
			while(lastr > curr){
				pair<ll, int> bad = mp(w[lastr], lastr);
				if(couldtake.find(bad) != couldtake.end()){
					couldtake.erase(bad);
				}
				if(taken.find(bad) != taken.end()){
					taken.erase(bad);
					cursum-=bad.f;
				}
				lastr--;
			}
			while(lastl > i){
				lastl--;
				couldtake.ins(mp(w[lastl], lastl));
			}
			while(sz(taken) < len){
				assert(sz(couldtake) > 0);
				pair<ll, int> good = *(prev(couldtake.end()));
				//put the best value into taken
				couldtake.erase(good);
				taken.ins(good);
				cursum+=good.f;
			}

			while(sz(couldtake)){
				pair<ll, int> best = *(prev(couldtake.end()));
				pair<ll, int> worst = *(taken.begin());
				if(best.f > worst.f){
					taken.erase(worst);
					cursum-=worst.f;
					taken.ins(best);
					cursum+=best.f;
					couldtake.erase(best);
					couldtake.ins(worst);
				}
				else break;
			}
		}
		ckmax(ans, cursum);

		/*if(len == 3){
			cout << "taken: ";
			for(auto u: taken){
				cout << u.f << " ";
			}
			cout << "\n";
			cout << "couldtake: ";
			for(auto u: couldtake){
				cout << u.f << " ";
			}
			cout << "\n";
		}*/
	}

	/*if(len == 3){
		cout << S << "\n";
		for(auto u: w){
			cout << u << " ";
		}
		cout << "\n";
		cout << ans << "\n";
	}*/

	return ans;
}

ll solvefixedlength(int len){
	if(len <= 0 || len > n) return 0;
	ll ans = 0;
	
	ckmax(ans, solvefixedlengthdirection(len));
	reversedir();
	ckmax(ans, solvefixedlengthdirection(len));
	return ans;
}

ll solverightonly(int L, int days){ //only move right from L
	set<pair<ll, int>> taken;
	ll ans = 0;
	ll cursum = 0;
	for(int i = L; i < n; i++){
		int num = days-(i-L);
		if(num <= 0) break;
		if(sz(taken) > num){
			assert(num == sz(taken)-1);
			pair<ll, int> lowest = *(taken.begin());
			taken.erase(lowest);
			cursum-=lowest.f;
		}
		pair<ll, int> couldtake = mp(w[i], i);
		if(sz(taken) < num){
			taken.ins(couldtake);
			cursum+=couldtake.f;
		}
		else{
			pair<ll, int> lowest = *(taken.begin());
			if(lowest.f < couldtake.f){
				taken.erase(lowest);
				cursum-=lowest.f;
				taken.ins(couldtake);
				cursum+=couldtake.f;
			}
		}
		ckmax(ans, cursum);
	}

	return ans;
}


ll solve(){ //go left, then right
	if(d == 0) return 0;
	ll ans = 0;
	ckmax(ans, solverightonly(S, d));
	
	reversedir();
	ckmax(ans, solverightonly(S, d));

	int lo = 1;
	int hi = min(n, d+1);

	while(hi-lo > 10){
		int mid1 = (2*lo+hi)/3;
		int mid2 = (2*hi+lo)/3;
		ll ans1 = solvefixedlength(mid1);
		ll ans2 = solvefixedlength(mid2);
		if(ans1 == 0){
			lo = mid1;
		}
		else if(ans2 == 0){
			hi = mid2;
		}
		else if(ans1 > ans2){
			hi = mid2;
		}
		else{
			lo = mid1;
		}
	}
	lo = (lo+hi)/2;

	for(int i = 0; i <= DIFF; i++){
		ckmax(ans, solvefixedlength(lo-i));
		ckmax(ans, solvefixedlength(lo+i));
	}

	return ans;
}

ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
	n = _n;
	S = start;
	d = _d;
	for(int i = 0; i < n; i++){
		w.pb(attraction[i]);
	}

    return solve();
}

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