Submission #52618

#	Time	Username	Problem	Language	Result	Execution time	Memory
52618		snat123	Art Exhibition (JOI18_art)	C++14	100 / 100	328 ms	17192 KiB

art

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<pair<long long, long long> > v;
    long long a, b, p[n], tmp[n], curr=0, ans=0;
    for(int i=0; i<n; i++){
    	cin >> a >> b;
    	v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    tmp[0]=p[0]=v[1].first-v[0].first-v[0].second;
    for(int i=1; i<n-1; i++){
    	p[i]=p[i-1]+v[i+1].first-v[i].first-v[i].second;
    	tmp[i]=max(tmp[i-1], p[i]);
    }
    curr=v[0].second;
    //cout << curr << endl;
    for(int i=0; i<n; i++){
    	if(i>0) curr+=(v[i].second-v[i].first+v[i-1].first);
    	//cout << i << " " << curr << endl;
    	ans=max(ans, curr);
    	if(i>0) ans=max(ans, curr+tmp[i-1]);
    }
    cout << ans;
    return 0;
} 

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