oj.uz

Submission #372947

# Submission time Handle Problem Language Result Execution time Memory
372947 2021-03-02T12:42:30 Z arujbansal Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 5832 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long

const int MXN = 1e5 + 5, INF = 1e16;

void solve() {
    int N, Q;
    cin >> N >> Q;

    vector<int> A(N + 1);
    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;

        vector<int> dp(N + 1, 0);
        int mx = -INF, mn = INF;

        for (int i = 1; i <= N; i++) {
            mx = max(mx, dp[i - 1] + A[i]);
            mn = min(mn, - dp[i - 1] + A[i]);

            dp[i] = max(dp[i], mx - A[i]);
            dp[i] = max(dp[i], A[i] - mn);

            dp[i] = max(dp[i], dp[i - 1]);
        }

        cout << dp[N] << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 86 ms 696 KB Output is correct
8 Correct 85 ms 492 KB Output is correct
9 Correct 87 ms 492 KB Output is correct
10 Correct 86 ms 492 KB Output is correct
11 Correct 84 ms 492 KB Output is correct
12 Correct 86 ms 668 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 86 ms 696 KB Output is correct
8 Correct 85 ms 492 KB Output is correct
9 Correct 87 ms 492 KB Output is correct
10 Correct 86 ms 492 KB Output is correct
11 Correct 84 ms 492 KB Output is correct
12 Correct 86 ms 668 KB Output is correct
13 Execution timed out 2045 ms 5832 KB Time limit exceeded
14 Halted 0 ms 0 KB -