제출 #985823

#제출 시각아이디문제언어결과실행 시간메모리
985823LOLOLOSjeckanje (COCI21_sjeckanje)C++14
15 / 110
2037 ms596 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 2e5 + 10; ll a[N]; ll cal(int n) { vector <ll> dp(n + 1, 0); for (int i = 1; i <= n; i++) { ll mx = a[i], mi = a[i]; for (int j = i; j >= 1; j--) { mx = max(mx, a[j]); mi = min(mi, a[j]); dp[i] = max(dp[i], dp[j - 1] + mx - mi); } } return dp[n]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 0; i < q; i++) { int l, r, x; cin >> l >> r >> x; for (int j = l; j <= r; j++) { a[j] += x; } cout << cal(n) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...