oj.uz

Submission #140635

# Submission time Handle Problem Language Result Execution time Memory
140635 2019-08-04T01:20:45 Z MatheusLealV Triple Jump (JOI19_jumps) C++17
46 / 100
 4000 ms 238004 KB 
#include <bits/stdc++.h>
#define N 500010
#define f first
#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(40, (int)val.size()); i++)
		{
			int vi = val[i].f, p = val[i].s;
 
			for(int x = 1; x <= n; x++)
			{
				if(x == p) continue;
				
				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]);
			}
 
			for(int x = 1; x < p; x++)
			{
				if(2*p - x > n) continue;
 
				int pp = query(1, 1, n, 2*p - x, n);
 
				ans = max(ans, pp + vi + v[x]);
			}
		}
 
		int a, b;
 
		cin>>a>>b;
 
		cout<<ans<<"\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 98680 KB Output is correct
2 Correct 84 ms 99484 KB Output is correct
3 Correct 83 ms 99448 KB Output is correct
4 Correct 83 ms 99448 KB Output is correct
5 Correct 83 ms 99448 KB Output is correct
6 Correct 83 ms 99436 KB Output is correct
7 Correct 83 ms 99448 KB Output is correct
8 Correct 84 ms 99516 KB Output is correct
9 Correct 83 ms 99448 KB Output is correct
10 Correct 83 ms 99428 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 98680 KB Output is correct
2 Correct 84 ms 99484 KB Output is correct
3 Correct 83 ms 99448 KB Output is correct
4 Correct 83 ms 99448 KB Output is correct
5 Correct 83 ms 99448 KB Output is correct
6 Correct 83 ms 99436 KB Output is correct
7 Correct 83 ms 99448 KB Output is correct
8 Correct 84 ms 99516 KB Output is correct
9 Correct 83 ms 99448 KB Output is correct
10 Correct 83 ms 99428 KB Output is correct
11 Correct 526 ms 237896 KB Output is correct
12 Correct 541 ms 237780 KB Output is correct
13 Correct 526 ms 237820 KB Output is correct
14 Correct 540 ms 237944 KB Output is correct
15 Correct 530 ms 238004 KB Output is correct
16 Correct 532 ms 237176 KB Output is correct
17 Correct 535 ms 237432 KB Output is correct
18 Correct 534 ms 237276 KB Output is correct
19 Correct 524 ms 237688 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2315 ms 5536 KB Output is correct
2 Correct 2165 ms 5356 KB Output is correct
3 Correct 1925 ms 5356 KB Output is correct
4 Correct 2256 ms 5360 KB Output is correct
5 Correct 2250 ms 5360 KB Output is correct
6 Correct 2270 ms 5356 KB Output is correct
7 Correct 2369 ms 6384 KB Output is correct
8 Correct 2371 ms 6384 KB Output is correct
9 Correct 2283 ms 6636 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 98680 KB Output is correct
2 Correct 84 ms 99484 KB Output is correct
3 Correct 83 ms 99448 KB Output is correct
4 Correct 83 ms 99448 KB Output is correct
5 Correct 83 ms 99448 KB Output is correct
6 Correct 83 ms 99436 KB Output is correct
7 Correct 83 ms 99448 KB Output is correct
8 Correct 84 ms 99516 KB Output is correct
9 Correct 83 ms 99448 KB Output is correct
10 Correct 83 ms 99428 KB Output is correct
11 Correct 526 ms 237896 KB Output is correct
12 Correct 541 ms 237780 KB Output is correct
13 Correct 526 ms 237820 KB Output is correct
14 Correct 540 ms 237944 KB Output is correct
15 Correct 530 ms 238004 KB Output is correct
16 Correct 532 ms 237176 KB Output is correct
17 Correct 535 ms 237432 KB Output is correct
18 Correct 534 ms 237276 KB Output is correct
19 Correct 524 ms 237688 KB Output is correct
20 Correct 2315 ms 5536 KB Output is correct
21 Correct 2165 ms 5356 KB Output is correct
22 Correct 1925 ms 5356 KB Output is correct
23 Correct 2256 ms 5360 KB Output is correct
24 Correct 2250 ms 5360 KB Output is correct
25 Correct 2270 ms 5356 KB Output is correct
26 Correct 2369 ms 6384 KB Output is correct
27 Correct 2371 ms 6384 KB Output is correct
28 Correct 2283 ms 6636 KB Output is correct
29 Execution timed out 4046 ms 15208 KB Time limit exceeded
30 Halted 0 ms 0 KB -