Submission #70857

#	Time	Username	Problem	Language	Result	Execution time	Memory
70857		someone_aa	Art Exhibition (JOI18_art)	C++17	100 / 100	870 ms	227116 KiB

art

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100;
map<ll, ll> sum;
vector<pair<ll, ll> > values;
vector<ll> pref;
ll n, x, y;

ll get_val(int l, int r) {
    ll sum =1LL* pref[r] - pref[l-1];
    ll diff = values[r].first - values[l].first;
    return sum - diff;
}

vector<pair<ll,ll> > temp;

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    cin>>n;
    temp.pb(mp(0,0));
    for(int i=0;i<n;i++) {
        cin>>x>>y;
        temp.pb(mp(x,y));
    }
    sort(temp.begin(), temp.end());
    values.pb(mp(0,0));
    for(int i=1;i<=n;i++) {
        if(temp[i].first != temp[i-1].first) {
            values.pb(mp(temp[i].first, temp[i].second));
        }
        else {
            values[values.size()-1].second += temp[i].second;
        }
    }

    pref.pb(0LL);
    for(int i=1;i<values.size();i++) {
        pref.pb(pref.back() + values[i].second);
    }

    ll l = 1LL;
    ll result = get_val(1,1);
    ll max_pref = values[1].first;
    for(ll i=2;i<values.size();i++) {
        max_pref = max(max_pref, values[i].first - pref[i-1]);
        ll curr_val = pref[i] - values[i].first + max_pref;
        result = max(result, curr_val);
    }
    cout<<result;

    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<values.size();i++) {
                 ~^~~~~~~~~~~~~~
art.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=2;i<values.size();i++) {
                ~^~~~~~~~~~~~~~
art.cpp:45:8: warning: unused variable 'l' [-Wunused-variable]
     ll l = 1LL;
        ^

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