oj.uz

Submission #159271

# Submission time Handle Problem Language Result Execution time Memory
159271 2019-10-22T00:09:07 Z socho Art Exhibition (JOI18_art) C++14
30 / 100
 1000 ms 1144 KB 
#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() {
	
	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 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 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 256 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 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 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 256 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 8 ms 376 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 8 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 376 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 404 KB Output is correct
23 Correct 8 ms 376 KB Output is correct
24 Correct 8 ms 396 KB Output is correct
25 Correct 8 ms 380 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 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 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 256 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 8 ms 376 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 8 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 376 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 404 KB Output is correct
23 Correct 8 ms 376 KB Output is correct
24 Correct 8 ms 396 KB Output is correct
25 Correct 8 ms 380 KB Output is correct
26 Correct 8 ms 376 KB Output is correct
27 Execution timed out 1079 ms 1144 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 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 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 256 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 8 ms 376 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 8 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 376 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 404 KB Output is correct
23 Correct 8 ms 376 KB Output is correct
24 Correct 8 ms 396 KB Output is correct
25 Correct 8 ms 380 KB Output is correct
26 Correct 8 ms 376 KB Output is correct
27 Execution timed out 1079 ms 1144 KB Time limit exceeded
28 Halted 0 ms 0 KB -