Submission #70849

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
70849	2018-08-23T14:11:36 Z	someone_aa	Art Exhibition (JOI18_art)	C++17	50 / 100	1000 ms	49612 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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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 = 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

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

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	560 KB	Output is correct
7	Correct	2 ms	676 KB	Output is correct
8	Correct	2 ms	676 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	3 ms	676 KB	Output is correct
11	Correct	2 ms	676 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	560 KB	Output is correct
7	Correct	2 ms	676 KB	Output is correct
8	Correct	2 ms	676 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	3 ms	676 KB	Output is correct
11	Correct	2 ms	676 KB	Output is correct
12	Correct	2 ms	676 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	3 ms	676 KB	Output is correct
15	Correct	3 ms	676 KB	Output is correct
16	Correct	3 ms	676 KB	Output is correct
17	Correct	3 ms	676 KB	Output is correct
18	Correct	3 ms	676 KB	Output is correct
19	Correct	3 ms	676 KB	Output is correct
20	Correct	3 ms	676 KB	Output is correct
21	Correct	3 ms	676 KB	Output is correct
22	Correct	2 ms	676 KB	Output is correct
23	Correct	3 ms	676 KB	Output is correct
24	Correct	3 ms	744 KB	Output is correct
25	Correct	2 ms	744 KB	Output is correct
26	Correct	2 ms	744 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	560 KB	Output is correct
7	Correct	2 ms	676 KB	Output is correct
8	Correct	2 ms	676 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	3 ms	676 KB	Output is correct
11	Correct	2 ms	676 KB	Output is correct
12	Correct	2 ms	676 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	3 ms	676 KB	Output is correct
15	Correct	3 ms	676 KB	Output is correct
16	Correct	3 ms	676 KB	Output is correct
17	Correct	3 ms	676 KB	Output is correct
18	Correct	3 ms	676 KB	Output is correct
19	Correct	3 ms	676 KB	Output is correct
20	Correct	3 ms	676 KB	Output is correct
21	Correct	3 ms	676 KB	Output is correct
22	Correct	2 ms	676 KB	Output is correct
23	Correct	3 ms	676 KB	Output is correct
24	Correct	3 ms	744 KB	Output is correct
25	Correct	2 ms	744 KB	Output is correct
26	Correct	2 ms	744 KB	Output is correct
27	Correct	7 ms	1132 KB	Output is correct
28	Correct	8 ms	1132 KB	Output is correct
29	Correct	7 ms	1132 KB	Output is correct
30	Correct	7 ms	1132 KB	Output is correct
31	Correct	8 ms	1132 KB	Output is correct
32	Correct	6 ms	1136 KB	Output is correct
33	Correct	6 ms	1136 KB	Output is correct
34	Correct	9 ms	1136 KB	Output is correct
35	Correct	7 ms	1136 KB	Output is correct
36	Correct	6 ms	1136 KB	Output is correct
37	Correct	6 ms	1136 KB	Output is correct
38	Correct	8 ms	1136 KB	Output is correct
39	Correct	7 ms	1228 KB	Output is correct
40	Correct	8 ms	1228 KB	Output is correct
41	Correct	7 ms	1228 KB	Output is correct
42	Correct	7 ms	1228 KB	Output is correct
43	Correct	7 ms	1228 KB	Output is correct
44	Correct	6 ms	1228 KB	Output is correct
45	Correct	8 ms	1228 KB	Output is correct
46	Correct	8 ms	1228 KB	Output is correct
47	Correct	7 ms	1228 KB	Output is correct
48	Correct	8 ms	1228 KB	Output is correct
49	Correct	7 ms	1228 KB	Output is correct
50	Correct	6 ms	1228 KB	Output is correct
51	Correct	6 ms	1228 KB	Output is correct

Subtask #4
0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	560 KB	Output is correct
7	Correct	2 ms	676 KB	Output is correct
8	Correct	2 ms	676 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	3 ms	676 KB	Output is correct
11	Correct	2 ms	676 KB	Output is correct
12	Correct	2 ms	676 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	3 ms	676 KB	Output is correct
15	Correct	3 ms	676 KB	Output is correct
16	Correct	3 ms	676 KB	Output is correct
17	Correct	3 ms	676 KB	Output is correct
18	Correct	3 ms	676 KB	Output is correct
19	Correct	3 ms	676 KB	Output is correct
20	Correct	3 ms	676 KB	Output is correct
21	Correct	3 ms	676 KB	Output is correct
22	Correct	2 ms	676 KB	Output is correct
23	Correct	3 ms	676 KB	Output is correct
24	Correct	3 ms	744 KB	Output is correct
25	Correct	2 ms	744 KB	Output is correct
26	Correct	2 ms	744 KB	Output is correct
27	Correct	7 ms	1132 KB	Output is correct
28	Correct	8 ms	1132 KB	Output is correct
29	Correct	7 ms	1132 KB	Output is correct
30	Correct	7 ms	1132 KB	Output is correct
31	Correct	8 ms	1132 KB	Output is correct
32	Correct	6 ms	1136 KB	Output is correct
33	Correct	6 ms	1136 KB	Output is correct
34	Correct	9 ms	1136 KB	Output is correct
35	Correct	7 ms	1136 KB	Output is correct
36	Correct	6 ms	1136 KB	Output is correct
37	Correct	6 ms	1136 KB	Output is correct
38	Correct	8 ms	1136 KB	Output is correct
39	Correct	7 ms	1228 KB	Output is correct
40	Correct	8 ms	1228 KB	Output is correct
41	Correct	7 ms	1228 KB	Output is correct
42	Correct	7 ms	1228 KB	Output is correct
43	Correct	7 ms	1228 KB	Output is correct
44	Correct	6 ms	1228 KB	Output is correct
45	Correct	8 ms	1228 KB	Output is correct
46	Correct	8 ms	1228 KB	Output is correct
47	Correct	7 ms	1228 KB	Output is correct
48	Correct	8 ms	1228 KB	Output is correct
49	Correct	7 ms	1228 KB	Output is correct
50	Correct	6 ms	1228 KB	Output is correct
51	Correct	6 ms	1228 KB	Output is correct
52	Execution timed out	1071 ms	49612 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

Submission #70849

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 50.0