Submission #752325

#	Time	Username	Problem	Language	Result	Execution time	Memory
752325		nicolaev	Art Exhibition (JOI18_art)	C++14	0 / 100	0 ms	212 KiB

art

#include <bits/stdc++.h>
using namespace std;
#define mod                1000000007
#define ll                 long long 
#define all(v)             v.begin(), v.end()
#define fr(n)              for(ll i=0;i<n;++i)
#define ctz(x)             __builtin_ctzll(x)
#define clz(x)             __builtin_clzll(x)
#define pcount(x)          __builtin_popcountll(x)
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
// #define cin fin
// #define cout fout
// ifstream fin
// ofstream fout
//const ll maxn = 3e5 + 5;
//int f[maxn],nf[maxn],inv[maxn];
//const int M=998244353;
//void init(){
//inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
//f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M;
//}
//int C(int x,int y){return 1ll*f[x]*nf[y]%M*nf[x-y]%M;}



void solve(){
    ll n;cin>>n;
    vector< pair<ll, ll> > v;
    ll sum=0;
    fr(n){
        ll a, b;cin>>a>>b;
        sum+=b;
        v.push_back(make_pair(a, b));
    }
    vector<ll> s;
    s.push_back(0);
    sort(all(v));
    sum-=v[n-1].first-v[0].first;
    for(ll i=0; i<n-1; i++){
        ll temp=v[i+1].first-v[i].first-v[i].second;
        s.push_back(temp+s[i]);
    }
    ll j=0;
    vector<ll> s2;s2.push_back(0);
    ll mx[n];
    mx[n-1]=0;
    for(ll i=n-1; i>0; i--){
        ll temp=v[i].first-v[i-1].first-v[i].second;
        s2.push_back(temp+s[j]);
        mx[i-1]=max(mx[i], temp+s[j]);
        j++;
    }
    ll ans=sum;
    // cout<<sum<<" ";
    // for(ll i=0; i<n; i++){
    //     cout<<mx[i]<<" ";
    // }
    for(ll i=0; i<n; i++){
        
        ans=max(ans, sum+s[i]+mx[i]);
    }
    cout<<ans;


}


int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL);
//    ll t;cin>>t;while(t--){solve();cout<<endl;}
    solve();
}

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