Submission #1070326

#TimeUsernameProblemLanguageResultExecution timeMemory
1070326VMaksimoski008Sjeckanje (COCI21_sjeckanje)C++17
15 / 110
2052 ms596 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n, q; cin >> n >> q; vector<ll> v(n+1), dp(n+1); for(int i=1; i<=n; i++) cin >> v[i]; while(q--) { int l, r, x; cin >> l >> r >> x; for(int i=l; i<=r; i++) v[i] += x; for(int i=2; i<=n; i++) { dp[i] = 0; ll mn=1e18, mx=-1e18; bool t = (v[i-1] >= v[i]); for(int j=i; j>=1; j--) { if(t == 1 && j < i && v[j] < v[i]) break; if(t == 0 && j < i && v[j] > v[i]) break; mn = min(mn, v[j]); mx = max(mx, v[j]); dp[i] = max(dp[i], dp[j-1] + mx - mn); } } cout << dp[n] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...