Submission #1115247

#TimeUsernameProblemLanguageResultExecution timeMemory
1115247staszic_ojuzArt Exhibition (JOI18_art)C++17
100 / 100
159 ms26736 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int64_t n, a, b;
    vector<pair<int64_t, int64_t>> obrazy;
    cin >> n;
    int64_t sumy[n + 1] = {0}, pref[n + 1];
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        obrazy.push_back({a, b});
    }
    //cout << endl;
    sort(obrazy.begin(), obrazy.end());
    pref[0] = obrazy[0].first;
    for(int i = 0; i < n; i++){
        a = obrazy[i].first;
        b = obrazy[i].second;
        sumy[i + 1] = sumy[i] + b;
        pref[i + 1] = max(pref[i], a - sumy[i]);
        //cout << sumy[i + 1] << " " << pref[i + 1] << " " << a << endl;
    }
    int64_t wyn = 0;
    //cout << endl;
    for(int i = 0; i < n; i++){
        wyn = max(wyn, sumy[i + 1] + pref[i + 1] - obrazy[i].first);
        //cout << sumy[i + 1] << " " << pref[i + 1] << " " << obrazy[i].first << endl;
    }
    cout << wyn;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...