oj.uz

Submission #203402

# Submission time Handle Problem Language Result Execution time Memory
203402 2020-02-20T13:33:34 Z oolimry Holiday (IOI14_holiday) C++14
100 / 100
 1973 ms 7288 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

///WLOG let's first go left to city L, and then right to city R. We can visit D - (S - L) - (R - L) attractions
///Let opt(L) refer to the optimal R for L. If L1 < L2, then opt(L1) <= opt(L2). Hence, we can use D&C optimization

///At each layer b, we try to find opt(L) for all L which are k * 2 ^ b where k is an odd number
///E.g. Layer two: 4; Layer one: 2, 6; Layer zero: 1, 3, 5;
///As we increase k, the R we need to try also only move forwards (and can only move forwards at most N times)

///We use multisets to keep track of which elements we take and which we don't take within our current range [L,R]
///Upon shrinking or expanding the range, we can update our multisets in O(logN) time
///Overal: O(NlogNlogN)

long long n, start, days;
long long arr[100005];
long long opt[100005];
long long ans = 0;

multiset<long long> take;
multiset<long long> notake;
long long value = 0;
long long canTake;

void include(long long pos){ ///expanding [L,R]
	if(pos > start) canTake--;
	else if(pos < start) canTake -= 2;
	
	take.insert(arr[pos]);
	value += arr[pos];
	
	while((long long) take.size() > max(canTake,0LL)){ ///move elements from take to notake
		multiset<long long>::iterator it = take.begin();
		value -= *it;
		notake.insert(*it);
		take.erase(it);
	}
}

void exclude(long long pos){ ///shrinking [L,R]
	if(pos > start) canTake++;
	else if(pos < start) canTake += 2;
	
	if(take.find(arr[pos]) != take.end()){
		take.erase(take.find(arr[pos]));
		value -= arr[pos];
	}
	else notake.erase(notake.find(arr[pos]));

	while((long long) take.size() < canTake){ ///move elements from notake to take
		if(notake.empty()) break;
		multiset<long long, greater<long long> >::iterator it = (--notake.end());
		value += *it;
		take.insert(*it);
		notake.erase(it);
	}
}

void reset(){
	take.clear();
	notake.clear();
	value = 0;
	canTake = days;
	include(start);
}

void solve(){
	for(long long bit = (1<<17);bit > 0;bit >>= 1){ ///D&C optimization
		if(bit > start) continue;
		
		reset();
		for(long long i = bit;i < start;i++) include(i);
		
		long long R = start + 1; ///next value not taken
		
		for(long long L = bit;L <= start;L += 2 * bit){
			
			long long endPoint;
			if(L + bit <= start) endPoint = opt[L + bit];
			else endPoint = n;
			
			long long best = value;
			long long bestR = opt[L - bit]; ///previous endpoint
			
			while(R <= endPoint){
				include(R);
				if(best < value){
					best = value;
					bestR = R;
				}
				R++;
			}
			
			opt[L] = bestR;
			ans = max(ans, best);
			
			for(long long i = L;i < min(start, L + 2 * bit);i++) exclude(i); ///consider the next value
		}
	}
}

long long findMaxAttraction(int N, int START, int DAYS, int ARR[]) {
	n = N;
	for(long long i = 0;i < n;i++) arr[i+1] = ARR[i]; ///1 - indexing for easier D&C
	start = START + 1;
	days = DAYS;
	
	reset();
	solve(); ///Go left, then go right
	
	reverse(arr+1,arr+(n+1));
	start = n - start + 1;
	reset();
	solve(); ///Go right, then go left
	
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 7288 KB Output is correct
2 Correct 778 ms 7032 KB Output is correct
3 Correct 750 ms 7032 KB Output is correct
4 Correct 792 ms 7160 KB Output is correct
5 Correct 1167 ms 6392 KB Output is correct
6 Correct 192 ms 2296 KB Output is correct
7 Correct 592 ms 3704 KB Output is correct
8 Correct 710 ms 4600 KB Output is correct
9 Correct 125 ms 1656 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 504 KB Output is correct
2 Correct 13 ms 632 KB Output is correct
3 Correct 13 ms 504 KB Output is correct
4 Correct 32 ms 504 KB Output is correct
5 Correct 28 ms 504 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 11 ms 376 KB Output is correct
9 Correct 11 ms 376 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 7288 KB Output is correct
2 Correct 513 ms 6904 KB Output is correct
3 Correct 557 ms 2784 KB Output is correct
4 Correct 25 ms 376 KB Output is correct
5 Correct 11 ms 376 KB Output is correct
6 Correct 11 ms 380 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 1965 ms 5368 KB Output is correct
9 Correct 1973 ms 5112 KB Output is correct