Submission #233067

#	Time	Username	Problem	Language	Result	Execution time	Memory
233067		oolimry	Cake 3 (JOI19_cake3)	C++14	100 / 100	3750 ms	15468 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define C first
#define V second
using namespace std;
typedef pair<long long, long long> ii;

int n, m; 

long long op[300005];
ii arr[200005];

struct maxM{
	multiset<int> take;
	multiset<int> notake;
	long long total = 0;
	int l = -1, r = -1;
	
	void include(long long pos){
		long long x = arr[pos].V;
		if(l == -1){ ///initialise first element
			l = pos; r = pos;
		}
		else r++; ///expand

		take.insert(x); total += x;
		if((int) take.size() > m){
			auto it = take.begin();
			total -= *it;
			take.erase(it);
			notake.insert(*it);
		}
	}
	
	void exclude(){
		long long x = arr[l].V;
		l++; ///contract
		
		auto it = notake.find(x);
		if(it != notake.end()){
			notake.erase(it);
			return;
		}
		
		take.erase(take.find(x)); total -= x;
		while((int) take.size() < m && !notake.empty()){
			auto it2 = (--notake.end());
			take.insert(*it2);
			total += *it2;
			notake.erase(it2);
		}
		
	}
	
	long long get(){
		if((int) take.size() == m) return total;
		else return -1e18;
	}
	
	void reset(){
		take.clear();
		notake.clear();
		l = -1, r = -1;
		total = 0;
	}
};
maxM S; ///Sliding window set: sum of the m largest integers in range [l,r]

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m; m -= 2;
	
	for(int i = 1;i <= n;i++) cin >> arr[i].V >> arr[i].C;
	sort(arr+1,arr+n+1);
	
	fill(op,op+300004, n); op[0] = 1; 
	long long ans = -1e18;
	
	for(int bit = (1<<17);bit >= 1;bit >>= 1){ ///D&C Optimization
		S.reset();
		
		for(int s = bit;s < n - m;s += 2*bit){
			int L, R;
			L = op[s-bit];
			R = op[s+bit];
			L = max(s+1, L);
			
			long long bestValue = -1e18;
			long long bestPos = -1;
			
			
			for(int e = L;e <= R;e++){
				
				long long val = S.get() + arr[s].V + arr[e].V - 2*arr[e].C + 2*arr[s].C;
				ans = max(ans, val);
				if(bestValue < val){
					bestValue = val;
					bestPos = e;
				}
				
				if(e != R){
					S.include(e);
				}
			}
			
			while(S.l <= s + 2*bit && S.l <= S.r){
				S.exclude();
			}
			op[s] = bestPos;
		}
	}
	
	cout << ans;	
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76