Submission #243313

#	Time	Username	Problem	Language	Result	Execution time	Memory
243313		rqi	휴가 (IOI14_holiday)	C++14	24 / 100	5072 ms	6124 KiB

holiday

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

typedef pair<int, int> pi;
typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;

#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 = 30;
int n;
int S;
int d;
vl w;

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

//////TOPK SECTION BEGINS
int k;
set<pi> indices;

void CLEAR(){
	indices.clear();
}

void INSERT(int ind){
    indices.ins(mp(w[ind], ind));
}	

void ERASE(int ind){
    indices.erase(mp(w[ind], ind));
}

ll getsum(){
	auto it = prev(indices.end());
	ll ans = 0;
	int num = 0;
	while(num < k){
		ans+=it->f;
		num++;
		if(it == indices.begin()) break;
		it = prev(it);
	}
	return ans;
}

//TOPK SECTION ENDS


ll solvefixedlengthdirection(int len){ //going left to right
	CLEAR();
	k = len;
	int days = d-len;
	int lastr = -5; //last r that is still in topk or couldtake
	ll ans = 0;
	for(int i = S; i >= 0; i--){
		int curr = (days-(S-i))+i;
		ckmin(curr, n-1);
		if(curr-i+1 < len) continue;

		if(lastr == -5){
			for(int j = i; j <= curr; j++){
				INSERT(j);
			}
			lastr = curr;
		}
		else{
			while(lastr > curr){
				ERASE(lastr);
				lastr--;
			}
			INSERT(i);
		}

		ckmax(ans, getsum());
		
	}
	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<pi> 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);
			pi lowest = *(taken.begin());
			taken.erase(lowest);
			cursum-=lowest.f;
		}
		pi couldtake = mp(w[i], i);
		if(sz(taken) < num){
			taken.ins(couldtake);
			cursum+=couldtake.f;
		}
		else{
			pi 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;
	clock_t c = clock();
	ll ans = 0;
	ckmax(ans, solverightonly(S, d));
	
	reversedir();
	ckmax(ans, solverightonly(S, d));
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
	int lo = 1;
	int hi = min(n, d+1);
	
	while(hi-lo > 3){
		int mid1 = (2*lo+hi)/3;
		int mid2 = (2*hi+lo)/3;
		ll ans1 = solvefixedlength(mid1);
		//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
		ll ans2 = solvefixedlength(mid2);
		//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
		if(ans1 == 0){
			lo = mid1;
		}
		else if(ans2 == 0){
			hi = mid2;
		}
		else if(ans1 > ans2){
			hi = mid2;
		}
		else{
			lo = mid1;
		}
	}
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
	lo = (lo+hi)/2;

	for(int i = 0; i <= DIFF; i++){
		ckmax(ans, solvefixedlength(lo-i));
		ckmax(ans, solvefixedlength(lo+i));
	}
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";

	return ans;
}

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

    return solve();
}

Compilation message (stderr)

holiday.cpp: In function 'll solve()':
holiday.cpp:144:10: warning: unused variable 'c' [-Wunused-variable]
  clock_t c = clock();
          ^

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