Submission #489489

#	Time	Username	Problem	Language	Result	Execution time	Memory
489489		8e7	Triple Jump (JOI19_jumps)	C++17	19 / 100	406 ms	72724 KiB

jumps

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 5005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], pref[maxn], suf[maxn], sp[19][maxn];
int ans[maxn][maxn];
pii ma[maxn];
int getma(int l, int r) {
	if (r < l) return 0;
	int len = __lg(r - l + 1);
	return max(sp[len][l], sp[len][r - (1<<len)+1]); 
}
int main() {
	io
	int n, q;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i], ma[i] = {a[i], i}, sp[0][i] = a[i];
	for (int i = 1;i <= n;i++) pref[i] = max(a[i], pref[i-1]);
	for (int i = n;i >= 1;i--) suf[i] = max(a[i], suf[i+1]);
	//sort(ma + 1, ma + n + 1, [&](pii x, pii y){return x.ff > y.ff;});
	for (int i = 1;i < 19;i++) {
		for (int j = 1;j <= n - (1<<i)+1;j++) {
			sp[i][j] = max(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = i + 2;j <= n;j++) {
			ans[i][j] = a[i] + a[j] + getma(i+1, (i+j)/2);
		}
	}
	for (int i = 2;i <= n;i++) {
		for (int j = 1;i + j <= n;j++) {
			ans[j][i+j] = max(ans[j][i+j], max(ans[j][i+j-1], ans[j+1][i+j]));
		}
	}
	cin >> q;
	/*
	if (q > 1) {
		return 0;
	}
	*/
	for (int i = 0;i < q;i++) {
		int l, r;
		cin >> l >> r;
		cout << ans[l][r] << "\n";	
	}
}
/*
5
5 2 1 5 3
1
1 5


5
5 4 4 5 4
1
1 5

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13
*/

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54