oj.uz

Submission #70823

# Submission time Handle Problem Language Result Execution time Memory
70823 2018-08-23T13:46:51 Z someone_aa Art Exhibition (JOI18_art) C++17
0 / 100
 3 ms 400 KB 
#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;
}

int main() {
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>x>>y;
        sum[x] += y;
    }

    values.pb(mp(0LL,0LL));
    pref.pb(0LL);
    for(auto i:sum) {
        values.pb(mp(i.first, i.second));
        pref.pb(pref.back() + i.second);
    }

    ll l = 1LL;
    ll result = 0LL;
    ll curr_val = 0LL;
    for(ll i=1;i<values.size();i++) {
        curr_val = get_val(l, i);
        while(l < i && get_val(l+1, i) > curr_val) {
            l++;
            curr_val = get_val(l, i);
        }
        result = max(result, curr_val);
    }
    cout<<result;

    return 0;
}

Compilation message

art.cpp: In function 'int main()':
art.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=1;i<values.size();i++) {
                ~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -