Submission #159272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159272	2019-10-22T00:10:00 Z	socho	Art Exhibition (JOI18_art)	C++14	30 / 100	1000 ms	1016 KB

art

#include "bits/stdc++.h"
using namespace std;

struct node {

   long long s, e, m, val;
   node *l, *r;
   node (long long _s, long long _e) {
       s = _s;
       e = _e;
       m = (s + e)/2;
       val = 0;
       if (s == e) return;
       l = new node(s, m);
       r = new node(m+1, e);
   }

   void upd(long long p, long long v) {
       if (s == p && s== e) {
           val = v;
           return;
       }
       if (p <= m) {
           l->upd(p, v);
       }
       else {
           r->upd(p, v);
       }
       val = l->val + r->val;
   }

   long long qry(long long qs, long long qe) {
       if (qs <= s && e <= qe) {
           return val;
       }
       else if (qs > e || s > qe) {
           return 0;
       }
       else {
           return l->qry(qs, qe) + r->qry(qs, qe);
       }
   }
} *root;

void init(long long N) {
   root = new node(0, N-1);
}

void update(long long P, long long V) {
   root->upd(P, V);
}

long long query(long long A, long long B) {
   return root->qry(A, B);
}

int main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	long long n;
	cin >> n;
	vector<pair<long long, long long> > works;
	for (long long i=0; i<n; i++) {
		long long siz, val;
		cin >> siz >> val;
		works.push_back(make_pair(siz, val));
	}
	sort(works.begin(), works.end());
	init(n);
	for (long long i=0; i<n; i++) {
		update(i, works[i].second);
	}
	long long best = LLONG_MIN;
	for (long long i=0; i<n; i++) {
		for (long long j=i; j<n; j++) {
			best = max(best, query(i, j) + works[i].first - works[j].first);
		}
	}
	cout << best << endl;
	
}

Subtask #1

10.0 / 10.0

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

Subtask #2

20.0 / 20.0

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

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	8 ms	460 KB	Output is correct
13	Correct	8 ms	376 KB	Output is correct
14	Correct	8 ms	376 KB	Output is correct
15	Correct	8 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	8 ms	376 KB	Output is correct
18	Correct	8 ms	376 KB	Output is correct
19	Correct	8 ms	460 KB	Output is correct
20	Correct	8 ms	376 KB	Output is correct
21	Correct	8 ms	376 KB	Output is correct
22	Correct	8 ms	376 KB	Output is correct
23	Correct	8 ms	380 KB	Output is correct
24	Correct	7 ms	376 KB	Output is correct
25	Correct	7 ms	376 KB	Output is correct
26	Correct	8 ms	376 KB	Output is correct
27	Execution timed out	1083 ms	1016 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	8 ms	460 KB	Output is correct
13	Correct	8 ms	376 KB	Output is correct
14	Correct	8 ms	376 KB	Output is correct
15	Correct	8 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	8 ms	376 KB	Output is correct
18	Correct	8 ms	376 KB	Output is correct
19	Correct	8 ms	460 KB	Output is correct
20	Correct	8 ms	376 KB	Output is correct
21	Correct	8 ms	376 KB	Output is correct
22	Correct	8 ms	376 KB	Output is correct
23	Correct	8 ms	380 KB	Output is correct
24	Correct	7 ms	376 KB	Output is correct
25	Correct	7 ms	376 KB	Output is correct
26	Correct	8 ms	376 KB	Output is correct
27	Execution timed out	1083 ms	1016 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-