Submission #418314

#	Time	Username	Problem	Language	Result	Execution time	Memory
418314		jasmin	Art Exhibition (JOI18_art)	C++14	100 / 100	226 ms	11988 KiB

art

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int,int> > bild(n);
    for(int i=0; i<n; i++){
        int s, v;
        cin >> s >> v;
        bild[i]={s, v};
    }
    sort(bild.begin(), bild.end());

    int mini=0;
    int maxi=0;
    vector<int> s(n);
    int summe=0;
    int ans=0;

    for(int i=0; i<n; i++){
        summe+=bild[i].second;
        s[i]=summe-(bild[i].first-bild[0].first);
        if(s[i]>maxi){
            maxi=s[i];
            ans=max(ans, maxi-mini);
        }
        if(i<n-1 && s[i]-(bild[i+1].first-bild[i].first)<mini){
            mini=s[i]-(bild[i+1].first-bild[i].first);
            maxi=mini;
        }
    }

    cout << ans << "\n";
}

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