oj.uz

Submission #1096506

# Submission time Handle Problem Language Result Execution time Memory
1096506 2024-10-04T16:24:57 Z tanduc111 Triple Jump (JOI19_jumps) C++14
19 / 100
 489 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, a[500005];
void solve()
{
	vector <vector<int>> f(n + 3, vector<int> (n + 3, 0));
	vector <vector<int>> dp(n + 3, vector<int> (n + 3, 0));
	for (int i = 1; i <= n; i++)
	{
		f[i][i] = a[i];
		for (int j = i + 1; j <= n; j++) f[i][j] = max(f[i][j - 1], a[j]);
	}
	for (int len = 2; len < n; len++)
		for (int i = 1; i + len <= n; i++)
		{
			int x = i, y = i + len;
			dp[x][y] = max({dp[x + 1][y], dp[x][y - 1], a[x] + a[y] + f[x + 1][(x + y)/2]});
		}
	int q; cin >> q;
	while (q--)
	{
		int l, r; cin >> l >> r;
		cout << dp[l][r] << '\n';
	}
}
signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 600 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 453 ms 402260 KB Output is correct
12 Correct 448 ms 402256 KB Output is correct
13 Correct 396 ms 402308 KB Output is correct
14 Correct 476 ms 402260 KB Output is correct
15 Correct 444 ms 402296 KB Output is correct
16 Correct 461 ms 401748 KB Output is correct
17 Correct 489 ms 401492 KB Output is correct
18 Correct 439 ms 401488 KB Output is correct
19 Correct 462 ms 402256 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 226 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 453 ms 402260 KB Output is correct
12 Correct 448 ms 402256 KB Output is correct
13 Correct 396 ms 402308 KB Output is correct
14 Correct 476 ms 402260 KB Output is correct
15 Correct 444 ms 402296 KB Output is correct
16 Correct 461 ms 401748 KB Output is correct
17 Correct 489 ms 401492 KB Output is correct
18 Correct 439 ms 401488 KB Output is correct
19 Correct 462 ms 402256 KB Output is correct
20 Runtime error 226 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -