Submission #1049775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049775		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	296 ms	16076 KiB

art

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <time.h>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <bits/stdc++.h>

#define speed ios_base::sync_with_stdio(0), cin.tie(0)
#define TxtIO freopen("points.in","r",stdin); freopen("points.out","w",stdout);
using namespace std;
const int mod = 998244353;
#define ll long long
const int N=2e5+5;

//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll binpow (ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)
			res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}




void fcn(){
	ll n;
	cin>>n;
	pair <ll,ll> a[n+3];
	ll dp[n+3],dp2[n+3];
	dp[0]=0;
	for (int i=1; i<=n; i++){
		cin>>a[i].first>>a[i].second;
	}
	
	sort(a+1,a+1+n);
	
	for (int i=1; i<=n; i++){	
		dp[i]=dp[i-1]+a[i].second;
	}
	
	dp2[0]=-1e18;
	ll ans=0;
	for (int i=1; i<=n; i++){
		dp2[i]=max(dp2[i-1],a[i].first-dp[i-1]);
	}
	
	for (int i=n; i>0; i--){
		ans=max(ans,dp[i]+dp2[i]-a[i].first);
	}
	
	cout<<ans;
	
	
	
	
	
	
	
}                        

int main(){
	//srand(time(0));
	//fflush(stdout);
//	freopen("bridges.in","r",stdin); freopen("bridges.out","w",stdout);
	
	
//	speed;
	ll T=1;
//	cin>>T;
	for (int i=1; i<=T; i++){
		fcn();	
	}
}




 

/*

1
2 3
4 5
6 7


*/

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