Submission #978793

#TimeUsernameProblemLanguageResultExecution timeMemory
978793mannshah1211Sjeckanje (COCI21_sjeckanje)C++17
55 / 110
2084 ms5952 KiB
/** * author: hashman * created: **/ #include <bits/stdc++.h> using namespace std; template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif using Int = long long; const Int inf = 1e18; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, tt; cin >> n >> tt; vector<Int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } while (tt--) { int l, r, x; cin >> l >> r >> x; for (int j = l; j <= r; j++) { a[j] += x; } vector<Int> dp(n + 1); Int mxsub = -inf, mxadd = -inf; for (int j = 1; j <= n; j++) { mxsub = max(mxsub, dp[j - 1] - a[j]); mxadd = max(mxadd, dp[j - 1] + a[j]); dp[j] = max(dp[j], mxsub + a[j]); dp[j] = max(dp[j], mxadd - a[j]); } cout << dp[n] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...