Submission #225188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225188	2020-04-19T13:15:34 Z	muhammad_hokimiyon	Art Exhibition (JOI18_art)	C++14	50 / 100	76 ms	13932 KB

#include <bits/stdc++.h>

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimize("Ofast")
//1.0 * clock() / CLOCKS_PER_SEC

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const ll NN = 1e10 + 7;
const int N = 2e5 + 7;
const int M = 6;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);

int n;
ll a[N];
ll b[N];
ll sum[N];

void solve1()
{
    cin >> n;
    vector < int > v;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i] >> b[i];
        v.push_back(i);
    }
    sort( v.begin() , v.end() , [&] ( int i , int j ){
        return a[i] < a[j];
    } );
    set < ll > s;
    for( int h = 1; h <= n; h++ ){
        int i = v[h - 1];
        sum[h] = sum[h - 1] + b[i];
    }
    ll ans = -1e18;
    for( int h = 1; h <= n; h++ ){
        int i = v[h - 1];
        s.insert( sum[h - 1] - a[i] );
        auto x = *s.begin();
        ans = max( ans , sum[h] - a[i] - x );
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int cghf = 1;//cin >> cghf;
    while( cghf-- ){
        solve1();
    }
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	4 ms	256 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	5 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct
23	Correct	5 ms	384 KB	Output is correct
24	Correct	5 ms	384 KB	Output is correct
25	Correct	5 ms	384 KB	Output is correct
26	Correct	5 ms	384 KB	Output is correct
27	Correct	8 ms	896 KB	Output is correct
28	Correct	7 ms	896 KB	Output is correct
29	Correct	7 ms	896 KB	Output is correct
30	Correct	8 ms	896 KB	Output is correct
31	Correct	7 ms	896 KB	Output is correct
32	Correct	9 ms	896 KB	Output is correct
33	Correct	8 ms	896 KB	Output is correct
34	Correct	8 ms	896 KB	Output is correct
35	Correct	7 ms	896 KB	Output is correct
36	Correct	9 ms	896 KB	Output is correct
37	Correct	7 ms	1024 KB	Output is correct
38	Correct	7 ms	896 KB	Output is correct
39	Correct	8 ms	896 KB	Output is correct
40	Correct	8 ms	896 KB	Output is correct
41	Correct	8 ms	896 KB	Output is correct
42	Correct	7 ms	896 KB	Output is correct
43	Correct	7 ms	896 KB	Output is correct
44	Correct	7 ms	896 KB	Output is correct
45	Correct	7 ms	896 KB	Output is correct
46	Correct	8 ms	896 KB	Output is correct
47	Correct	7 ms	896 KB	Output is correct
48	Correct	7 ms	896 KB	Output is correct
49	Correct	8 ms	896 KB	Output is correct
50	Correct	8 ms	896 KB	Output is correct
51	Correct	8 ms	896 KB	Output is correct
52	Runtime error	76 ms	13932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Halted	0 ms	0 KB	-

Submission #225188

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