Submission #1083935

#TimeUsernameProblemLanguageResultExecution timeMemory
1083935duytuandao21Sjeckanje (COCI21_sjeckanje)C++17
15 / 110
2044 ms536 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e6 + 7; const int inf = 1e9 + 7; const long long infll = 1e18 + 7; int n, q; long long a[N]; long long GetResult() { vector<long long> dp(n + 1, 0); vector<long long> minAt(n + 1, infll); vector<long long> maxAt(n + 1, -infll); long long res = -infll; for (int i = 1; i <= n; i++) { for (int j = i; j > 0; j--) { minAt[j] = min(minAt[j], a[i]); maxAt[j] = max(maxAt[j], a[i]); dp[i] = max(dp[i], dp[j - 1] + maxAt[j] - minAt[j]); res = max(res, dp[i]); } } return res; } int 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; long long v; cin >> l >> r >> v; for (int i = l; i <= r; i++) a[i] += v; cout << GetResult(); if (q > 0) cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...