Submission #1013045

#TimeUsernameProblemLanguageResultExecution timeMemory
1013045aliarapovTriple Jump (JOI19_jumps)C++17
5 / 100
4046 ms33152 KiB
#include <bits/stdc++.h> #define int long long #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() using namespace std; const int INF = 1e9; const int mod = 998244353; const int N = 200005; int sp[N][20]; int get(int l, int r){ int lg = __lg(r - l + 1); return max(sp[l][lg], sp[r - (1ll << lg) + 1][lg]); } void solve(){ int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } for(int i = 0; i < n; i++){ sp[i][0] = a[i]; } for(int i = 1; i < 20; i++){ for(int j = 0; j < n; j++){ sp[j][i] = max(sp[j][i - 1], sp[min(n - 1, j + (1ll << (i - 1)))][i - 1]); } } int q; cin >> q; while(q--){ int l, r; cin >> l >> r; l--; r--; int ans = 0; for(int i = l; i < r - 1; i++){ for(int j = i + 1; j < r; j++){ if(j + (j - i) <= r) ans = max(ans, a[i] + a[j] + get(j + (j - i), r)); } } cout << ans << '\n'; } } main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while(tt--){ solve(); } }

Compilation message (stderr)

jumps.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...