This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define xn '\n'
#define pb push_back
#define oo LONG_MAX
using namespace std;
typedef pair<ll,ll> i2;
typedef pair<ll,i2> i3;
typedef pair<i2,ll> i4;
const int N = 1e5+5;
const int M = 1e3+5;
const ll mo = 1e9+7;
ll n,m;
ll a[N];
ll c[N];
ll d[N];
ll res;
stack <ll> s;
void sub3(){
ll l,r; cin >> l >> r;
for (long i=n; i>=1; i--) c[i] = max(c[i+1],a[i]);
for (long i=1; i<=n; i++){
ll j1 = 0;
while (!s.empty() && a[i] > a[s.top()]) s.pop();
if (!s.empty()) j1 = s.top();
s.push(i);
if (j1 != 0 && i + i - j1 <= n) res = max(res,a[j1]+a[i]+c[i+i-j1]);
}
while (!s.empty()) s.pop();
for (long i=n; i>=1; i--){
ll j1 = 0;
while (!s.empty() && a[i] > a[s.top()]) s.pop();
if (!s.empty()) j1 = s.top();
s.push(i);
if (j1 != 0 && j1 + j1 - i <= n) res = max(res,a[j1]+a[i]+c[j1 + j1 - i]);
}
cout << res;
}
void sub1(){
while (m--){
ll l,r; cin >> l >> r;
ll ans = 0;
for (int i=l; i<=r-2; i ++){
for (int j=i+1; j<=r-1 ;j++){
for (int k=j+(j-i); k<=r ; k++){
ans = max(ans , a[i] + a[j] + a[k]);
}
}
}
cout << ans << xn;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (long i=1; i<=n; i++) cin >> a[i];
cin >> m;
if (m != 1) sub1(); else sub3();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |