Submission #1103039

#TimeUsernameProblemLanguageResultExecution timeMemory
1103039duonggsimpTriple Jump (JOI19_jumps)C++14
5 / 100
4078 ms4944 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...