Submission #140635

#	Time	Username	Problem	Language	Result	Execution time	Memory
140635		MatheusLealV	Triple Jump (JOI19_jumps)	C++17	46 / 100	4046 ms	238004 KiB

jumps

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54