Submission #547977

#	Time	Username	Problem	Language	Result	Execution time	Memory
547977		Aktan	Art Exhibition (JOI18_art)	C++14	100 / 100	235 ms	24816 KiB

art

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ft first
#define sc second
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const int mod=1e9+7,INF=1e17,N=5e5+5;

int pr[N];
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vector<pair<int,int>> v;
	for(int i=0;i<n;i++){
		int a,b;
		cin >> a >> b;
		v.push_back({a,b});
	}
	sort(v.begin(),v.end());
	int ans=0,mx=-INF;
	for(int i=0;i<n;i++){
		if(i==0){
			pr[i]=v[i].sc;
		}
		else{
			pr[i]=pr[i-1]+v[i].sc;
		}
	}
	for(int i=0;i<n;i++){
		if(i==0){
			mx=max(mx,v[i].ft-0);
			ans=max(ans,pr[i]-v[i].ft+mx);
		}
		else{
			mx=max(mx,v[i].ft-pr[i-1]);
			ans=max(ans,pr[i]-v[i].ft+mx);
		}	
	}
	cout << ans;
	
}

Compilation message (stderr)

art.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      | ^~~~

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