Submission #138045

#	Time	Username	Problem	Language	Result	Execution time	Memory
138045		rajarshi_basu	Cake 3 (JOI19_cake3)	C++14	0 / 100	4090 ms	376 KiB

cake3

#include <bits/stdc++.h>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>

using namespace std;

const int MAXN = 2e5 + 1;
const ll INF = 1e17;

int n,m;

ll color[MAXN];
ll v[MAXN];
ll dp[MAXN];
int lptr = 0;
int rptr  = -1;
set<ll> s1;
set<ll> s2;

void add(int ptr){
	//cout << ptr << endl;
	s1.insert(v[ptr]);
	if(s1.size() > m){
		ll v = *s1.begin();
		s1.erase(s1.begin());
		s2.insert(v);
	}
}
void remove(int ptr){
	//cout << ptr << endl;
	if(s2.find(v[ptr]) != s2.end()){
		s2.erase(s2.find(v[ptr]));
	}else{
		s1.erase(s1.find(v[ptr]));
		if(!s2.empty()){
			auto it = s2.end();
			it--;
			s1.insert(*it);
			s2.erase(it);
		}
	}
	return;
	if(s2.size() > 0)s2.erase(s2.begin());
	else s1.erase(s1.begin());
}

ll cost(int l,int r){
	if(s1.size() < m)return -INF;
	ll sum = 0;
	for(auto e:s1)sum += e;
	return sum;
	/*vv<ll> a;
	FORE(i,l,r)a.pb(v[i]);
	sort(a.begin(),a.end());reverse(a.begin(),a.end());
	if(a.size() < m)return -INF;
	ll sum = 0;
	FOR(i,m)sum += a[i];
	return sum;*/
}

void recurse(int l,int r,int x,int y){
	int mid = (l+r)/2;
	ll mx = -INF;
	int optj = x;
	while(rptr != mid){
		if(rptr > mid){
			remove(rptr--);
		}else{
			add(++rptr);
		}
	}
	while(lptr != x){
		if(lptr > x){
			add(--lptr);
		}else{
			remove(lptr++);
		}
	}
	
	FORE(i,x,min(mid,y)){
		if(i > lptr)remove(lptr++);
		ll cst = cost(i,mid) - 2*(color[mid] - color[i]);
		if(cst > mx){
			optj = i;
			mx = cst;
		}
	}
	dp[mid] = mx;
	if(l == r)return;
	recurse(l,mid,x,optj);
	recurse(mid+1,r,optj,y);
}

int main(){
	cin >> n >> m;
	vv<ii> all;
	FOR(i,n){
		int a,b;
		cin >> a >> b;
		all.pb({b,a});
	}
	sort(all.begin(),all.end());
	FOR(i,n)color[i] = all[i].ff,v[i] = all[i].ss;
	recurse(0,n-1,0,n-1);
	ll mx = -INF;
	FOR(i,n){
		mx = max(mx,dp[i]);
	}
	cout << mx << endl;
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void add(int)':
cake3.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(s1.size() > m){
     ~~~~~~~~~~^~~
cake3.cpp: In function 'long long int cost(int, int)':
cake3.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(s1.size() < m)return -INF;
     ~~~~~~~~~~^~~

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