oj.uz

Submission #512700

# Submission time Handle Problem Language Result Execution time Memory
512700 2022-01-16T16:48:53 Z kartel Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 55 ms 3096 KB 
#include <bits/stdc++.h>
#define blue 0
#define red 1
#define purple 2
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
#define el "\n"
using namespace std;
typedef long long ll;

const int N = 1e5 + 500;

ll a[N], f[N][2], b[N];
int n, q;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        b[i] = a[i + 1] - a[i];
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        b[l - 1] += x;
        b[r] -= x;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 2; j++) {
                f[i][j] = -1e18;
            }
        }
        f[1][0] = 0;
        f[1][1] = abs(b[1]);
        for (int i = 2; i < n; i++) {
            if ((b[i - 1] < 0 && b[i] < 0) || (b[i - 1] > 0 && b[i] > 0)) {
                f[i][1] = max(f[i][1], f[i - 1][1] + abs(b[i]));
            }
            f[i][1] = max(f[i - 1][0] + abs(b[i]), f[i][1]);
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        }
        cout << max(f[n - 1][0], f[n - 1][1]) << el;
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 54 ms 504 KB Output is correct
8 Correct 54 ms 492 KB Output is correct
9 Correct 55 ms 492 KB Output is correct
10 Correct 53 ms 544 KB Output is correct
11 Correct 53 ms 488 KB Output is correct
12 Correct 52 ms 492 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 54 ms 504 KB Output is correct
8 Correct 54 ms 492 KB Output is correct
9 Correct 55 ms 492 KB Output is correct
10 Correct 53 ms 544 KB Output is correct
11 Correct 53 ms 488 KB Output is correct
12 Correct 52 ms 492 KB Output is correct
13 Runtime error 37 ms 3096 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -