oj.uz

Submission #140614

# Submission time Handle Problem Language Result Execution time Memory
140614 2019-08-03T19:21:48 Z MatheusLealV Triple Jump (JOI19_jumps) C++17
19 / 100
 2722 ms 437084 KB 
#include <bits/stdc++.h>
#define N 500010
#define f first
#define int long long
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, q, v[N], C[5010][5010], menor[5010][5010], dp[5010][5010];

int ans, tree[4*N];

void build(int nod, int a, int b)
{
	if(a == b)
	{
		tree[nod] = v[a];

		return;
	}

	build(2*nod, a, (a+b)/2);

	build(2*nod + 1, (a + b)/2 + 1, b);

	tree[nod] = max(tree[2*nod], tree[2*nod + 1]);
}

int query(int nod, int a, int b, int i, int j)
{
	if(j < a or i > b) return 0;

	if(i <= a and j >= b) return tree[nod];

	return max(query(2*nod, a, (a+b)/2, i, j), query(2*nod + 1, (a+b)/2 + 1, b, i, j));
}

int solve(int i, int j)
{
	if(i > j) return 0;

	if(dp[i][j] != -1) return dp[i][j];

	return dp[i][j] = max({solve(i + 1, j), solve(i, j - 1), C[i][j]});
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 1; i <= n; i++) cin>>v[i];

	if(n <= 5000)
	{
		memset(dp, -1, sizeof dp);

		for(int i = 1; i <= n; i++)
		{
			menor[i][i] = v[i];

			for(int j = i + 1; j <= n; j++)
				menor[i][j] = max(menor[i][j - 1], v[j]);
		}

		for(int i = 1; i <= n; i++)
		{
			for(int j = i + 1; j <= n; j++)
			{
				int mid = (i + j)/2;

				C[i][j] = menor[i + 1][mid] + v[i] + v[j];
			}
		}

		cin>>q;

		for(int i = 1, l, r; i <= q; i++)
		{
			cin>>l>>r;

			cout<<solve(l, r)<<"\n";
		}
	}

	else
	{
		build(1, 1, n);

		vector<pii> val;

		for(int i = 1; i <= n; i++) val.push_back({v[i], i});

		sort(val.rbegin(), val.rend());

		for(int i = 0; i < min(50LL, (int)val.size()); i++)
		{
			int vi = val[i].f, p = val[i].s;

			for(int x = 1; x <= n; x++)
			{
				int mid = (x + p)/2;

				int l = min(x, p), r = max(x, p);

				int opt = query(1, 1, n, l + 1, mid);

				ans = max(ans, opt + v[l] + v[r]);
			}
		}

		int a, b;

		cin>>a>>b;

		cout<<ans<<"\n";
	}
}

Compilation message

jumps.cpp: In function 'int32_t main()':
jumps.cpp:99:8: warning: unused variable 'vi' [-Wunused-variable]
    int vi = val[i].f, p = val[i].s;
        ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 196856 KB Output is correct
2 Correct 163 ms 197752 KB Output is correct
3 Correct 160 ms 197752 KB Output is correct
4 Correct 162 ms 197852 KB Output is correct
5 Correct 161 ms 197752 KB Output is correct
6 Correct 160 ms 197880 KB Output is correct
7 Correct 162 ms 197752 KB Output is correct
8 Correct 164 ms 197832 KB Output is correct
9 Correct 159 ms 197752 KB Output is correct
10 Correct 159 ms 197728 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 196856 KB Output is correct
2 Correct 163 ms 197752 KB Output is correct
3 Correct 160 ms 197752 KB Output is correct
4 Correct 162 ms 197852 KB Output is correct
5 Correct 161 ms 197752 KB Output is correct
6 Correct 160 ms 197880 KB Output is correct
7 Correct 162 ms 197752 KB Output is correct
8 Correct 164 ms 197832 KB Output is correct
9 Correct 159 ms 197752 KB Output is correct
10 Correct 159 ms 197728 KB Output is correct
11 Correct 700 ms 436816 KB Output is correct
12 Correct 697 ms 436964 KB Output is correct
13 Correct 703 ms 437028 KB Output is correct
14 Correct 689 ms 437084 KB Output is correct
15 Correct 698 ms 436984 KB Output is correct
16 Correct 713 ms 436472 KB Output is correct
17 Correct 695 ms 436220 KB Output is correct
18 Correct 730 ms 436216 KB Output is correct
19 Correct 710 ms 436728 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2493 ms 11396 KB Output is correct
2 Correct 2722 ms 11496 KB Output is correct
3 Correct 2384 ms 11368 KB Output is correct
4 Correct 2546 ms 11368 KB Output is correct
5 Correct 2578 ms 11368 KB Output is correct
6 Incorrect 2677 ms 11372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 196856 KB Output is correct
2 Correct 163 ms 197752 KB Output is correct
3 Correct 160 ms 197752 KB Output is correct
4 Correct 162 ms 197852 KB Output is correct
5 Correct 161 ms 197752 KB Output is correct
6 Correct 160 ms 197880 KB Output is correct
7 Correct 162 ms 197752 KB Output is correct
8 Correct 164 ms 197832 KB Output is correct
9 Correct 159 ms 197752 KB Output is correct
10 Correct 159 ms 197728 KB Output is correct
11 Correct 700 ms 436816 KB Output is correct
12 Correct 697 ms 436964 KB Output is correct
13 Correct 703 ms 437028 KB Output is correct
14 Correct 689 ms 437084 KB Output is correct
15 Correct 698 ms 436984 KB Output is correct
16 Correct 713 ms 436472 KB Output is correct
17 Correct 695 ms 436220 KB Output is correct
18 Correct 730 ms 436216 KB Output is correct
19 Correct 710 ms 436728 KB Output is correct
20 Correct 2493 ms 11396 KB Output is correct
21 Correct 2722 ms 11496 KB Output is correct
22 Correct 2384 ms 11368 KB Output is correct
23 Correct 2546 ms 11368 KB Output is correct
24 Correct 2578 ms 11368 KB Output is correct
25 Incorrect 2677 ms 11372 KB Output isn't correct
26 Halted 0 ms 0 KB -