Submission #206414

#TimeUsernameProblemLanguageResultExecution timeMemory
206414stefdascaArt Exhibition (JOI18_art)C++14
100 / 100
263 ms28792 KiB
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;
typedef long long ll;

int n;
pair<ll, int> v[500002];
ll sp[500002], mxx[500002];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> v[i].fi >> v[i].se;
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; ++i)
    {
        sp[i] = sp[i-1] + v[i-1].fi + v[i].se - v[i].fi;
      //  cout << sp[i] << " ";
    }
   // cout << '\n';
    mxx[n] = sp[n];
    for(int i = n-1; i >= 1; --i)
        mxx[i] = max(mxx[i+1], sp[i]);
    ll ans = 0;
    for(int i = 1; i <= n; ++i)
    {
       // cout << mxx[i] + v[i].fi << " " << - sp[i-1] - v[i-1].fi << '\n';
        ans = max(ans, mxx[i] + v[i].fi - sp[i-1] - v[i-1].fi);
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...