Submission #66751

#	Time	Username	Problem	Language	Result	Execution time	Memory
66751		quoriess	Art Exhibition (JOI18_art)	C++14	100 / 100	883 ms	30440 KiB

art

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
vector<pii> arts;
const int MAXN=5*1e5+5;
#define  boy first;
#define  value second;
int main(){
	int n;
	cin>>n;
	vector<lli> prefVal(n);

	lli ans=-10;
	for (int i = 0; i < n; i++)
	{
		pii a;
		cin>>a.first>>a.second;
		ans=max(ans,a.second);
		arts.push_back(a);
	}
	sort(arts.begin(),arts.end());
	vector<lli> minim(n,0),minimaxi(n,0);
	minimaxi[0]=minim[0]=arts[0].first;
	vector<lli> prefmin(n,0),prefminmax(n,0);
	prefminmax[0]=prefmin[0]=arts[0].first;

	for (int i = 0; i < n; i++)
	{
		pii a=arts[i];
		if(i==0)prefVal[0]=a.second;
		else prefVal[i]=prefVal[i-1]+a.second;
		if(i!=0){
			minim[i]=arts[i].first-arts[i-1].first-arts[i-1].second;
			minimaxi[i]=max(minimaxi[i-1],minim[i]);
			prefmin[i]=prefmin[i-1]+minim[i];
			prefminmax[i]=max(prefminmax[i-1],prefmin[i]);
		}
	}
	for (int i = 1; i < n; i++)
	{
		lli snc=prefVal[i]-arts[i].first+prefminmax[i];
		ans=max(snc,ans);
	}


	cout <<ans<<"\n";
	return 0;
}

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