Submission #1013024

#TimeUsernameProblemLanguageResultExecution timeMemory
1013024Alihan_8Triple Jump (JOI19_jumps)C++17
19 / 100
246 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' #define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector <int> a(n + 1); for ( int i = 1; i <= n; i++ ){ cin >> a[i]; } vector <vector<int>> dp(n + 2, vector <int> (n + 2)); for ( int i = n - 2; i > 0; i-- ){ int k = i + 1, mx = 0; for ( int j = i + 2; j <= n; j++ ){ dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); while ( k < j && k - i <= j - k ){ chmax(mx, a[k]); k++; } chmax(dp[i][j], mx + a[i] + a[j]); } } int q; cin >> q; while ( q-- ){ int l, r; cin >> l >> r; cout << dp[l][r] << ln; } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...