Submission #66738

#	Time	Username	Problem	Language	Result	Execution time	Memory
66738		quoriess	Art Exhibition (JOI18_art)	C++14	0 / 100	2 ms	248 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;
int main(){
	int n;
	cin>>n;
	vector<lli> prefVal(n);
	for (int i = 0; i < n; i++)
	{
		pii a;
		cin>>a.first>>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;
	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]);
		}
	}
	lli ans=-10;
	for (int i = 1; i < n; i++)
	{
		lli snc=prefVal[i]-arts[i].first+minimaxi[i];
		ans=max(snc,ans);
	}


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


/*#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
vector<pii> arts;
int main(){
	int n;
	cin>>n;
	vector<lli> prefVal(n);
	for (int i = 0; i < n; i++)
	{
		pii a;
		cin>>a.first>>a.second;
		arts.push_back(a);
	}
	sort(arts.begin(),arts.end());
	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;
	}
	vector<int> opt(n,0),optDeger(n,0);
	lli ans=0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			lli snc=prefVal[j]-(i==0?0:prefVal[i-1])+arts[i].first-arts[j].first;
			if(snc>optDeger[j]){
				optDeger[j]=snc;
				opt[j]=i;
			}
			if(snc>ans)
			{
				ans=snc;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << "opt: "<<i<<":"<< opt[i]<<"\n";
	}

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

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