Submission #1321834

#TimeUsernameProblemLanguageResultExecution timeMemory
1321834hasanArt Exhibition (JOI18_art)C++20
0 / 100
0 ms336 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long

void solve(){
    int n;
    cin >> n;
    vector<array<ll,2>> k(n);
    map<ll,ll> kk;
    for(auto& [a,b]:k){
        cin >> a >> b;
        kk[a]+=b;
    }
    vector<array<ll,2>> k1;
    for(auto [l1,r]:kk) k1.push_back({l1,r});
    int l=0;
    ll s=0;
    ll max1=-1000000000000000000;
    for(int i=0; i<k1.size(); i++){
        s+=k1[i][1];
        while(l<i && s-(k1[i][0]-k1[l+1][0])-k1[l][1]>=s-(k1[i][0]-k1[l][0])){
            s-=k1[l][0];
            l++;
        }
        max1=max(max1,s-(k1[i][0]-k1[l][0]));
    }
    cout << max1;
}

signed main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...