Submission #932546

#TimeUsernameProblemLanguageResultExecution timeMemory
932546a_l_i_r_e_z_aSjeckanje (COCI21_sjeckanje)C++17
55 / 110
39 ms648 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back // #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() #define len(x) ((int)(x).size()) const int maxn = 3000 + 5; const int inf = 1e9 + 7; ll n, q, a[maxn], dp[maxn], b[maxn]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i]; while(q--){ int l, r, x; cin >> l >> r >> x; for(int i = l; i <= r; i++) a[i] += x; dp[1] = 0; dp[2] = abs(a[2] - a[1]); b[2] = 1; for(int i = 3; i <= n; i++){ dp[i] = dp[i - 1]; if((a[i] >= a[i - 1]) == (a[i - 1] >= a[i - 2])) b[i] = b[i - 1]; else b[i] = i - 1; smax(dp[i], abs(a[i] - a[b[i]]) + dp[b[i] - 1]); smax(dp[i], abs(a[i] - a[b[i] + 1]) + dp[b[i]]); } cout << dp[n] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...