Submission #206414

#	Time	Username	Problem	Language	Result	Execution time	Memory
206414		stefdasca	Art Exhibition (JOI18_art)	C++14	100 / 100	263 ms	28792 KiB

art

#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;
}

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