제출 #489440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489440		8e7	Triple Jump (JOI19_jumps)	C++17	0 / 100	44 ms	6060 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 500005
#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];
pii ma[maxn];
int main() {
	io
	int n, q;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i], ma[i] = {a[i], 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;});
	cin >> q;
	if (q > 1) {
		return 0;
	}
	for (int i = 0;i < q;i++) {
		int l, r;
		cin >> l >> r;
		int ans = 0;
		for (int j = 1;j <= min(n, 20);j++) {
			int id = ma[j].ss, val = ma[j].ff;
			for (int k = 1;k < id;k++) {
				if (2*id - k <= n) ans = max(ans, val + a[k] + suf[2*id-k]);	
				if (k>1) ans = max(ans, val + a[k] + pref[k-1]); 
			}
			for (int k = id + 1;k < n;k++) {
				if (2*k - id <= n) ans = max(ans, val + a[k] + suf[2*k-id]);
			}
		}
		cout << ans << endl;
	}
}
/*
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: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54