Submission #877828

#	Time	Username	Problem	Language	Result	Execution time	Memory
877828		raul2008487	Art Exhibition (JOI18_art)	C++17	100 / 100	149 ms	36708 KiB

art

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;
const int sz = 2e6+6;
const int mod = 1e9+7;
const ll inf = 1000000000;
void solve(){
    ll n, i, j, ans = 0, res = 0, sum = 0;
    cin>>n;
    vl a(n), b(n), pre(n+1), suf(n+1);
    vector<pair<ll,ll>> v;
    for(i=0;i<n;i++){
        cin>>a[i]>>b[i];
        v.pb({a[i], b[i]});
        ans = max(ans, b[i]);
        sum += b[i];
    }
    sort(all(v));
    sum = (sum - (v.back().fi - v[0].fi));
    ///cout << sum << endl;
    pre[0] = (v[1].fi - v[0].fi - v[0].se);
    for(i=1;i<n-1;i++){
        pre[i] = pre[i-1] + (v[i+1].fi - v[i].fi - v[i].se);
        //pre[i] = max(pre[i], pre[i-1]);
    }
    for(i=1;i<n-1;i++){
        pre[i] = max(pre[i-1], pre[i]);
    }
    res = max(res, pre[n-2]);
    suf[n-1] = ((v[n-1].fi - v[n-2].fi) - v[n-1].se);
    for(i=n-2;i>0;i--){
        suf[i] = suf[i+1] + (v[i].fi - v[i-1].fi - v[i].se);
    }
    for(i=n-2;i>0;i--){
        suf[i] = max(suf[i], suf[i+1]);
    }
    res = max(res, suf[1]);
    //cout << pre[n-2] << ' ' << suf[1] << endl;
    for(i=1;i<n-1;i++){
        res = max(res, (pre[i-1] + suf[i+1]));
    }
    cout << (sum + res) << endl;

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //precomp();
    ll tst=1;
    //cin>>tst;
    while(tst--){
        solve();
    }
}
/*
6
4 1
1 5
10 3
9 1
4 2
5 3

*/

Compilation message (stderr)

art.cpp: In function 'void solve()':
art.cpp:20:14: warning: unused variable 'j' [-Wunused-variable]
   20 |     ll n, i, j, ans = 0, res = 0, sum = 0;
      |              ^

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