Submission #106038

#	Time	Username	Problem	Language	Result	Execution time	Memory
106038		he_____he	Art Exhibition (JOI18_art)	C++14	100 / 100	214 ms	24824 KiB

art

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct node{
	ll x,y;
	bool operator<(const node c)const{
		if(x==c.x) return y<c.y;
		return x<c.x;
	}
}k[500005];

ll n;
ll s[500005];

int main(){
	n=readint();
	for(int i=1;i<=n;i++) k[i].x=readint(),k[i].y=readint();
	sort(k+1,k+n+1);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+k[i].y;
	ll ans=0,now=0;
	for(int i=1;i<=n;i++){
		now=max(now,k[i].x-s[i-1]);
		ans=max(ans,s[i]-k[i].x+now);
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50