oj.uz

Submission #163933

# Submission time Handle Problem Language Result Execution time Memory
163933 2019-11-16T09:59:46 Z maruii Triple Jump (JOI19_jumps) C++14
19 / 100
 1002 ms 77324 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

const int SIZE = 1 << 15;
struct ST {
	int A[2 * SIZE];
	void update(int x, int v) {
		for (x += SIZE; x; x >>= 1) A[x] = max(A[x], v);
	}
	int query(int s, int e) {
		int ret = 0;
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) ret = max(ret, A[s++]);
			if (~e & 1) ret = max(ret, A[e--]);
		}
		return ret;
	}
} seg;

int A[5005], X[5005][5005];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	if (N > 5000) assert(0);
	for (int i = 1; i <= N; ++i) cin >> A[i], seg.update(i, A[i]);

	for (int i = 2; i < N; ++i) {
		for (int j = 1; j + i <= N; ++j) {
			X[j][j + i] = max({X[j][j + i - 1], X[j + 1][j + i], seg.query(j + 1, j + i / 2) + A[j] + A[j + i]}); 
		}
	}

	int Q; cin >> Q;
	for (int i = 0; i < Q; ++i) {
		int s, e; cin >> s >> e;
		printf("%d\n", X[s][e]);
	}
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 764 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 1002 ms 77068 KB Output is correct
12 Correct 956 ms 77200 KB Output is correct
13 Correct 950 ms 77204 KB Output is correct
14 Correct 958 ms 77324 KB Output is correct
15 Correct 950 ms 77176 KB Output is correct
16 Correct 950 ms 76476 KB Output is correct
17 Correct 955 ms 76552 KB Output is correct
18 Correct 955 ms 76536 KB Output is correct
19 Correct 984 ms 77068 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 764 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 1002 ms 77068 KB Output is correct
12 Correct 956 ms 77200 KB Output is correct
13 Correct 950 ms 77204 KB Output is correct
14 Correct 958 ms 77324 KB Output is correct
15 Correct 950 ms 77176 KB Output is correct
16 Correct 950 ms 76476 KB Output is correct
17 Correct 955 ms 76552 KB Output is correct
18 Correct 955 ms 76536 KB Output is correct
19 Correct 984 ms 77068 KB Output is correct
20 Runtime error 7 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -