Submission #1180193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180193		ByeWorld	Cake 3 (JOI19_cake3)	C++20	24 / 100	4091 ms	7088 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 1e9;
const int INF = 2e9+100;
const int SQRT = 500;
const int LOG = 19;
const int MOD = 998244353;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int sum(int a, int b){ a %= MOD; b %= MOD; return (a+b)%MOD; }
void chsum(int &a, int b){ a %= MOD; b %= MOD; a = (a+b)%MOD; }
void chsub(int &a, int b){ a %= MOD; b %= MOD; a = (a+MOD-b)%MOD; }
int mul(int a, int b){ a %= MOD; b %= MOD; return a*b%MOD;}
void chmul(int &a, int b){ a = a*b%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te);
}

struct segtree {
	int st[4*MAXN];
	void bd(int id,int l, int r){
		st[id] = INF;
		if(l==r) return;
		bd(lf,l,md); bd(rg,md+1,r);
	}
	int que(int id,int l, int r,int x,int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return INF;
		return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	int upd(int id,int l, int r,int x,int y){
		if(l==r && l==x) return st[id] = y;
		if(r<x || x<l) return st[id];
		return st[id] = min(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} MN;
struct seg {
	int st[4*MAXN];
	void bd(int id,int l, int r){
		st[id] = -INF;
		if(l==r) return;
		bd(lf,l,md); bd(rg,md+1,r);
	}
	int que(int id,int l, int r,int x,int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return -INF;
		return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	int upd(int id,int l, int r,int x,int y){
		if(l==r && l==x) return st[id] = y;
		if(r<x || x<l) return st[id];
		return st[id] = max(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} MX;

int n, m, dep[MAXN], val[MAXN];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	vector<pii> vec;
	for(int i=1; i<=n; i++){
		int a, b;cin>>a>>b;
		vec.pb({b,a});
	}
	sort(vec.begin(), vec.end());
	for(int i=1; i<=n; i++){
		val[i] = vec[i-1].se; dep[i] = vec[i-1].fi;
		// cout << i << ' ' << val[i] << ' ' << dep[i] << " dep\n";
	}
	int ANS = -INF;
	for(int r=m; r<=n; r++){
		priority_queue<int,vector<int>,greater<int>> pq;
		int bet = 0; // ambil r sm l, diantara ambil m-2
		for(int l=r-1; l>=r-m+2; l--){
			bet += val[l]; pq.push(val[l]);
		}
		for(int l=r-m+1; l>=1; l--){
			int te = val[r]+val[l]+bet - 2*(dep[r]-dep[l]);
			chmx(ANS, te);
			bet += val[l]; pq.push(val[l]);
			bet -= pq.top(); pq.pop();
		}
	}
	cout << ANS << '\n';
} 

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