oj.uz

Submission #489440

# Submission time Handle Problem Language Result Execution time Memory
489440 2021-11-23T02:03:14 Z 8e7 Triple Jump (JOI19_jumps) C++17
0 / 100
 44 ms 6060 KB 
//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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 0 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 0 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6060 KB Output is correct
2 Correct 27 ms 5984 KB Output is correct
3 Correct 27 ms 5968 KB Output is correct
4 Incorrect 41 ms 5992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 0 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -