Submission #881475

#	Time	Username	Problem	Language	Result	Execution time	Memory
881475		theghostking	Art Exhibition (JOI18_art)	C++17	100 / 100	955 ms	80000 KiB

art

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    int n;
    cin >> n;
    map<int,int> mp;
    for (int i = 0; i<n; i++){
        int a,b;
        cin >> a >> b;
        mp[a] += b;
    }
    vector<pair<int,int>> vec;
    for (auto u : mp){
        vec.push_back(u);
    }
    sort(vec.begin(),vec.end());
    int sz = vec.size();
    int pf[sz+1];
    pf[0] = 0;
    multiset<int> ms;
    for (int i = 1; i<=sz; i++){
        pf[i] = pf[i-1] + vec[i-1].second;
        ms.insert(pf[i]-vec[i-1].first);
    }
    //set of pf[i] - vec[i-1].first
    //get max of that
    int bst = 0;
    for (int i = 1; i<=sz; i++){
        //start from i
        int cr = vec[i-1].first - pf[i-1];
        auto it = ms.rbegin();
        int val = *it;
        bst = max(bst, cr + val);
        ms.erase(ms.find(pf[i]-vec[i-1].first));
    }
    cout << bst;
    return 0;
}

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