// Muallif: Azimjon Mehmonali o'g'li
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = 1e18;
const int N = 500500;
int a[N], t[4 * N];
// void build(1)
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// build();
int q;
cin >> q;
function<int(int, int)> f = [&](int l, int r) {
// cerr << l << " " << r << endl;
if (r - l + 1 <= 2) return 0ll;
vector<pair<int, int>> v;
for (int i = l; i <= r; i++) {
v.emplace_back(a[i], i);
}
sort(v.rbegin(), v.rend());
int tl = v[0].second, tr = v[1].second;
if (tl > tr) {
swap(tl, tr);
}
int re = 0;
for (int i = 1; i <= n; i++) {
vector<int> d{tl, tr, i};
sort(d.begin(), d.end());
if (i == tl || i == tr || l > i || i > r
|| d[2] - d[1] < d[1] - d[0])
continue;
re = max(re, a[i]);
}
return max({v[0].first + v[1].first + re, f(l, v[0].second - 1),
f(v[0].second + 1, r)});
};
while (q--) {
int l, r;
cin >> l >> r;
cout << f(l, r) << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
8 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
8 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4075 ms |
6576 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
8 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |