Submission #260503

#	Time	Username	Problem	Language	Result	Execution time	Memory
260503		Bill_00	Art Exhibition (JOI18_art)	C++14	100 / 100	296 ms	28796 KiB

art

#include <bits/stdc++.h>
typedef long long ll;
#define fr(i,c,d) for(ll i=c;i<=d;i++)
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
//int h[200001],p[200001];
//int sum[100001];
//pair<ll,ll>p[100001];
//pair<ll,ll>p1[100001];
//string s;
string str(string x,int l,int r){
	string h;
	for(int i=l;i<=r;i++){
		h+=x[i];
	}
	return h;
}
ll res[500001],ans[500001];
pair<ll,ll>p[500001];
int main(){
	//int color[200001];
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	for(int i=1;i<=n;i++){
		ll a,b;
		cin >> a >> b;
		p[i]=mp(a,b);
	}
	sort(p+1,p+n+1);
	res[n]=0,ans[1]=0;
	for(int i=n-1;i>=1;i--){
		res[i]=max((ll)0,res[i+1])+p[i+1].ss-(p[i+1].ff-p[i].ff);
	}
	for(int i=2;i<=n;i++){
		ans[i]=max((ll)0,ans[i-1])+p[i-1].ss-(p[i].ff-p[i-1].ff);
	}
	ll hariu=-1e9;
	for(int i=1;i<=n;i++){
		ll k=p[i].ss;
		k+=max((ll)0,res[i]);
		k+=max((ll)0,ans[i]);
		hariu=max(hariu,k);
	}
	cout << hariu;
}	

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