#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt int
const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e9;
const intt mxN = 5e5 + 5;
const intt L = 21;
void solve() {
intt N, Q;
cin >> N >> Q;
vector<intt> A(N);
for(auto &a : A) cin >> a;
while(Q--){
intt l, r, val;
cin >> l >> r >> val;
--l; --r;
for(intt i = l; i <= r; i++) {
A[i] += val;
}
vector<intt> dp(N, 0ll);
dp[0] = 0;
// for(intt i = 0; i < N; i++) {
// cout << A[i] << " ";
// }
// cout << endl;
for(intt i = 1; i < N; i++) {
intt maks = A[i], mini = A[i];
for(intt j = i - 1; j >= 0; j--) {
maks = max(maks, A[j]);
mini = min(mini, A[j]);
if(j - 1 >= 0)
dp[i] = max(dp[i], dp[j-1] + abs(maks - mini));
else
dp[i] = max(dp[i], abs(maks - mini));
// if(i == 3 && j == 2) {
// cout << maks << " " << mini << " ALKSNFKL" << endl;
// }
}
}
cout << dp[N-1] << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
intt tst = 1;
// cin >> tst;
while(tst--) {
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |