oj.uz

Submission #932684

# Submission time Handle Problem Language Result Execution time Memory
932684 2024-02-24T03:11:54 Z ShadowShark Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 8880 KB 
#include <bits/stdc++.h>
using namespace std;

   ///***Author: ShadowShark***\\\
Con thuyen nho vuot muon trung nui non

const int maxN = 2e5 + 5;
long long a[maxN], d[maxN], dp[maxN][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("sjeckanje.inp", "r", stdin);
   // freopen("sjeckanje.out", "w", stdout);

    int n, q;
    cin >> n >> q;

    long long sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= q; i++) {
        int l, r, x;
        cin >> l >> r >> x;

        for (int i = l; i <= r; i++)
            a[i] += x;

        for (int i = 1; i < n; i++) {
            d[i] = a[i] - a[i + 1];
            sum = sum + abs(d[i]);
        }
        d[n] = 0; dp[0][0] = 0; dp[0][1] = 0;

        for (int i = 1; i < n ; i++){
            dp[i][0]= max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1]= max(dp[i - 1][0], dp[i - 1][1] * (d[i] * d[i - 1] >= 0)) + abs(d[i]);
        }

        cout << max(dp[n - 1][0], dp[n - 1][1]) << '\n';
    }

    return 0;
}

Compilation message

Main.cpp:4:4: warning: multi-line comment [-Wcomment]
    4 |    ///***Author: ShadowShark***\\\
      |    ^

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 37 ms 2700 KB Output is correct
8 Correct 37 ms 2692 KB Output is correct
9 Correct 36 ms 2652 KB Output is correct
10 Correct 42 ms 2908 KB Output is correct
11 Correct 36 ms 2684 KB Output is correct
12 Correct 37 ms 2648 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 37 ms 2700 KB Output is correct
8 Correct 37 ms 2692 KB Output is correct
9 Correct 36 ms 2652 KB Output is correct
10 Correct 42 ms 2908 KB Output is correct
11 Correct 36 ms 2684 KB Output is correct
12 Correct 37 ms 2648 KB Output is correct
13 Execution timed out 2054 ms 8880 KB Time limit exceeded
14 Halted 0 ms 0 KB -