Submission #1115247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115247		staszic_ojuz	Art Exhibition (JOI18_art)	C++17	100 / 100	159 ms	26736 KiB

art

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

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