oj.uz

Submission #941002

# Submission time Handle Problem Language Result Execution time Memory
941002 2024-03-08T04:55:22 Z shoryu386 Triple Jump (JOI19_jumps) C++17
19 / 100
 1159 ms 403480 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) ((int)x.size())

#define MAX 5007
int denseTable[MAX][MAX];
main(){ ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x];
	
	for (int x = 0; x < n; x++){
		
		int carry = arr[x];
		for (int y = x; y < n; y++){
			carry = max(arr[y], carry);
			denseTable[x][y] = carry;
		}
	}
	
	int results[n][n]; memset(results, 0, sizeof(results));
	for (int a = 0; a < n; a++){
		for (int c = a+2; c < n; c++){
			int endpt = (a+c)/2;
			results[a][c] = arr[a] + arr[c] + denseTable[a+1][endpt];
		}
	}
	
	for (int sz = 1; sz <= n; sz++){
		for (int x = 0; x+sz-1 < n; x++){
			if (x+sz < n) results[x][x+sz] = max(results[x][x+sz], results[x][x+sz-1]);
			if (x != 0) results[x-1][x+sz-1] = max(results[x-1][x+sz-1], results[x][x+sz-1]);
		}
	}
	
	int q; cin >> q;
	for (int x = 0; x < q; x++){
		int ql, qr; cin >> ql >> qr; ql--; qr--;
		cout << results[ql][qr] << '\n';
	}
}

Compilation message

jumps.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){ ios_base::sync_with_stdio(0); cin.tie(0);
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 546 ms 383872 KB Output is correct
12 Correct 442 ms 392148 KB Output is correct
13 Correct 481 ms 392240 KB Output is correct
14 Correct 456 ms 392036 KB Output is correct
15 Correct 454 ms 392068 KB Output is correct
16 Correct 467 ms 391728 KB Output is correct
17 Correct 480 ms 391572 KB Output is correct
18 Correct 466 ms 391576 KB Output is correct
19 Correct 452 ms 393828 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1159 ms 403480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 546 ms 383872 KB Output is correct
12 Correct 442 ms 392148 KB Output is correct
13 Correct 481 ms 392240 KB Output is correct
14 Correct 456 ms 392036 KB Output is correct
15 Correct 454 ms 392068 KB Output is correct
16 Correct 467 ms 391728 KB Output is correct
17 Correct 480 ms 391572 KB Output is correct
18 Correct 466 ms 391576 KB Output is correct
19 Correct 452 ms 393828 KB Output is correct
20 Runtime error 1159 ms 403480 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -