Submission #1321349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321349		spetr	Art Exhibition (JOI18_art)	C++20	100 / 100	140 ms	25468 KiB

art

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >>n;
    vector<pl> nums;
    for (ll i= 0; i < n; i++){
        ll a, b;
        cin >>a >> b;
        nums.push_back({a,b});
    }

    sort(nums.begin(), nums.end());
    vl p(n+1,0);
    for (ll i = 0; i < n; i++){
        p[i+1] = p[i] + nums[i].second;
    }

    vl v1, v2;
    for (ll i = 0; i < n; i++){
        v1.push_back(-nums[i].first + nums[i].second + p[i]);
        v2.push_back(nums[i].first + nums[i].second - p[i+1]);
    }

    ll maximum = 0;
    ll optimum = 0;
    for (ll i = 0; i < n; i++){
        optimum = max(optimum, nums[i].second);
    }
    for (ll i = 0; i < n; i++){
        optimum = max(optimum, v1[i]+maximum);
        maximum = max(maximum, v2[i]);
    }
    cout << optimum << "\n";



    return 0;
}

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