Submission #867980

#TimeUsernameProblemLanguageResultExecution timeMemory
867980ComGa999msSjeckanje (COCI21_sjeckanje)C++17
55 / 110
2040 ms8948 KiB
#include <bits/stdc++.h> #define all(v) (v).begin(), (v).end() #define int long long #define rep(i, l, r) for (int i = l; i <= r; ++i) #define repd(i, r, l) for (int i = r; i >= l; --i) #define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin()); #define sz(v) (int)(v).size() #define fi first #define se second #define pb push_back #define pf push_front #define mp make_pair #define eps double(1e-9) #define vii vector<int> #define pii pair<int,int> #define p2i pair<int,pii> #define endl '\n' using namespace std; const int N = 1e6 + 5; const int MN = 2e3 + 5; const int mod = 1e9 + 7; const int inf = 1e18 + 7; const bool Emily = false; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l, int r) { return l+rng()%(r-l+1); } bool minimize(int &a, int b) { if (a > b) { a = b; return 1; } return 0; } bool maximize(int &a, int b) { if (a < b) { a = b; return 1; } return 0; } int n, q; int a[N], dp[N]; int temp1, temp2; void solve(void) { cin >> n >> q; rep(i, 1, n) cin >> a[i]; while (q--) { int l, r, x; cin>> l >> r >> x; rep(i, l, r) a[i] += x; temp1 = temp2 = -inf; rep(i, 1, n) { maximize(temp1, dp[i - 1] - a[i]); maximize(temp2, dp[i - 1] + a[i]); dp[i] = max(temp1 + a[i], temp2 - a[i]); } cout << dp[n] << endl; } } signed main() { #define task "RECIPE" ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (Emily) { int t; cin >> t; while (t-- ) solve(); } else solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...