제출 #140620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140620		MatheusLealV	3단 점프 (JOI19_jumps)	C++17	19 / 100	2319 ms	238044 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++)
			{
				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: 0 / 27
• Subtask 4: 0 / 54