#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int maxn = 2e5 + 5;
const int oo = 1e9 + 7;
const ll inf = 1e18;
int n, q;
ll a[maxn], st[4*maxn], dp[maxn];
void sub1() { // O(n^2 * q)
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[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 0;
ll mx = a[i];
ll mn = a[i];
for (int j = i; j >= 1; j--) {
mx = max(mx, a[j]);
mn = min(mn, a[j]);
dp[i] = max(dp[i], mx - mn + dp[j - 1]);
}
}
cout << dp[n] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
sub1();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2384 KB |
Output is correct |
2 |
Correct |
5 ms |
2384 KB |
Output is correct |
3 |
Correct |
5 ms |
2384 KB |
Output is correct |
4 |
Correct |
5 ms |
2384 KB |
Output is correct |
5 |
Correct |
5 ms |
2528 KB |
Output is correct |
6 |
Correct |
6 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2384 KB |
Output is correct |
2 |
Correct |
5 ms |
2384 KB |
Output is correct |
3 |
Correct |
5 ms |
2384 KB |
Output is correct |
4 |
Correct |
5 ms |
2384 KB |
Output is correct |
5 |
Correct |
5 ms |
2528 KB |
Output is correct |
6 |
Correct |
6 ms |
2396 KB |
Output is correct |
7 |
Execution timed out |
2057 ms |
2552 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2384 KB |
Output is correct |
2 |
Correct |
5 ms |
2384 KB |
Output is correct |
3 |
Correct |
5 ms |
2384 KB |
Output is correct |
4 |
Correct |
5 ms |
2384 KB |
Output is correct |
5 |
Correct |
5 ms |
2528 KB |
Output is correct |
6 |
Correct |
6 ms |
2396 KB |
Output is correct |
7 |
Execution timed out |
2057 ms |
2552 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |