oj.uz

Submission #140616

# Submission time Handle Problem Language Result Execution time Memory
140616 2019-08-03T19:24:38 Z MatheusLealV Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 436332 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(100LL, (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 165 ms 196856 KB Output is correct
2 Correct 176 ms 197692 KB Output is correct
3 Correct 186 ms 197744 KB Output is correct
4 Correct 177 ms 197752 KB Output is correct
5 Correct 166 ms 197800 KB Output is correct
6 Correct 164 ms 197752 KB Output is correct
7 Correct 164 ms 197776 KB Output is correct
8 Correct 165 ms 197880 KB Output is correct
9 Correct 164 ms 197772 KB Output is correct
10 Correct 164 ms 197752 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 196856 KB Output is correct
2 Correct 176 ms 197692 KB Output is correct
3 Correct 186 ms 197744 KB Output is correct
4 Correct 177 ms 197752 KB Output is correct
5 Correct 166 ms 197800 KB Output is correct
6 Correct 164 ms 197752 KB Output is correct
7 Correct 164 ms 197776 KB Output is correct
8 Correct 165 ms 197880 KB Output is correct
9 Correct 164 ms 197772 KB Output is correct
10 Correct 164 ms 197752 KB Output is correct
11 Correct 691 ms 436128 KB Output is correct
12 Correct 751 ms 436076 KB Output is correct
13 Correct 728 ms 436332 KB Output is correct
14 Correct 749 ms 436092 KB Output is correct
15 Correct 726 ms 436108 KB Output is correct
16 Correct 743 ms 435396 KB Output is correct
17 Correct 718 ms 435412 KB Output is correct
18 Correct 696 ms 435564 KB Output is correct
19 Correct 699 ms 436088 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4061 ms 10216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 196856 KB Output is correct
2 Correct 176 ms 197692 KB Output is correct
3 Correct 186 ms 197744 KB Output is correct
4 Correct 177 ms 197752 KB Output is correct
5 Correct 166 ms 197800 KB Output is correct
6 Correct 164 ms 197752 KB Output is correct
7 Correct 164 ms 197776 KB Output is correct
8 Correct 165 ms 197880 KB Output is correct
9 Correct 164 ms 197772 KB Output is correct
10 Correct 164 ms 197752 KB Output is correct
11 Correct 691 ms 436128 KB Output is correct
12 Correct 751 ms 436076 KB Output is correct
13 Correct 728 ms 436332 KB Output is correct
14 Correct 749 ms 436092 KB Output is correct
15 Correct 726 ms 436108 KB Output is correct
16 Correct 743 ms 435396 KB Output is correct
17 Correct 718 ms 435412 KB Output is correct
18 Correct 696 ms 435564 KB Output is correct
19 Correct 699 ms 436088 KB Output is correct
20 Execution timed out 4061 ms 10216 KB Time limit exceeded
21 Halted 0 ms 0 KB -