Submission #1109188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109188		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	233 ms	16424 KiB

art

#include <bits/stdc++.h>

#define int long long

using namespace std;

pair<int,int> a[500005];
int pf[500005];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("MBP.inp","r",stdin);
//    freopen("MBP.out","w",stdout);
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
        v.push_back(a[i].first);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 1; i <= n; i++) a[i].first = lower_bound(v.begin(), v.end(), a[i].first) - v.begin() + 1;

    int ans = 0;
    for(int i = 1; i <= n; i++) pf[a[i].first] += a[i].second;
    for(int i = 1; i <= v.size(); i++){
        ans = max(ans, pf[i]);
        pf[i] += pf[i-1];
    }

    int maxx = 1e9;
    for(int i = 1; i <= v.size(); i++){
        ans = max(ans, pf[i] - v[i-1] - maxx);
        //cout << maxx << ' ' << i << ' ' << v[i-1] << endl;
        maxx = min(maxx, pf[i-1] - v[i-1]);
    }

    cout << ans;
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:29:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 1; i <= v.size(); i++){
      |                    ~~^~~~~~~~~~~
art.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 1; i <= v.size(); i++){
      |                    ~~^~~~~~~~~~~

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