Submission #810839

#	Time	Username	Problem	Language	Result	Execution time	Memory
810839		nemethm	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	212 KiB

art

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

const ll mod = 1e9 + 7;
vector<ll> pf;
vector<pair<ll,ll>> v;

ll sum(int l, int r){
    if(l == 0) return pf[r];
    return pf[r] - pf[l - 1];
}

ll eval(int l, int r){
    if(l > r) return -1;
    return sum(l, r)- (v[r].first - v[l].first);
}

int main(){
    int n;
    cin >> n;
    vector<pair<ll, ll>> temp(n);
    for(auto& i : temp){
        cin >> i.first >> i.second;
    }
    sort(begin(temp), end(temp));
    int i = 0;
    while(i < n){
        ll s = temp[i].second;
        while(i + 1 < n && temp[i + 1].first == temp[i].first){
            ++i;
            s += temp[i].second;
        }
        v.push_back({temp[i].first, s});
        ++i;
    }
    sort(begin(v), end(v));
    n = v.size();
    pf.resize(n);
    pf[0] = v[0].second;
    for(int i = 1; i < n; ++i){
        pf[i] = pf[i - 1] + v[i].second;
    }
    ll sol = 0;
    int l = 0, r = 0;
    while(r < n){
        while(l < r && eval(l + 1, r) > eval(l, r)){
            ++l;
        }
        sol = max(sol, eval(l, r));
        ++r;
    }
    cout << sol << endl;
    return 0;
}

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