Submission #411048

#	Time	Username	Problem	Language	Result	Execution time	Memory
411048		alireza_kaviani	Cake 3 (JOI19_cake3)	C++11	24 / 100	4075 ms	29320 KiB

cake3

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , m , sum , curl = 1 , curr = 0 , V[MAXN] , C[MAXN] , ans[MAXN];
vector<pll> vec;
set<pll> st1;
set<pll , greater<pll>> st2;

void balance(){
	while((SZ(st1) && SZ(st2) && (*st1.begin()) < (*st2.begin())) || SZ(st1) > m - 2){
		sum -= (*st1.begin()).X;
		st2.insert((*st1.begin()));
		st1.erase(st1.begin());
	}
	while(SZ(st1) < m - 2 && 0 < SZ(st2)){
		sum += (*st2.begin()).X;
		st1.insert((*st2.begin()));
		st2.erase(st2.begin());
	}
}

void insert(int i){
	st1.insert({V[i] , i}); sum += V[i];
	balance();
//	cout << "insert " << i << sep << sum << endl;
}

void remove(int i){
	if(st1.find({V[i] , i}) != st1.end()){
		st1.erase({V[i] , i}); sum -= V[i];
	}
	else{
		st2.erase({V[i] , i});
	}
	balance();
//	cout << "remove " << i << sep << sum << endl;
}

void move(int l , int r){
	while(curr < r)	insert(++curr);
	while(l < curl)	insert(--curl);
	while(r < curr)	remove(curr--);
	while(curl < l)	remove(curl++);
}

void solve(int l , int r , int optl , int optr){
	if(r < l)	return;
	int mid = l + r >> 1 , opt = -1;
	for(int i = optl ; i <= min(optr , mid - (int)m + 1) ; i++){
		move(i + 1 , mid - 1);
//		cout << i << sep << mid << sep << sum << endl;
		if(sum + V[mid] + V[i] - C[mid] + C[i] > ans[mid]){
			ans[mid] = sum + V[mid] - C[mid] + V[i] + C[i];
			opt = i;
		}
	}
	solve(l , mid - 1 , optl , opt);
	solve(mid + 1 , r , opt , optr);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	fill(ans , ans + MAXN , -INF);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i++){
		cin >> V[i] >> C[i];
		vec.push_back({C[i] , V[i]});
	}
	sort(all(vec));
	for(int i = 1 ; i <= n ; i++){
		C[i] = vec[i - 1].X * 2;
		V[i] = vec[i - 1].Y;
	}
	solve(m , n , 1 , n);
	ll res = -INF;
	for(int i = 1 ; i <= n ; i++)	res = max(res , ans[i]);
	cout << res << endl;

    return 0;
}
/*

*/

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1 , opt = -1;
      |            ~~^~~

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