oj.uz

Submission #513861

# Submission time Handle Problem Language Result Execution time Memory
513861 2022-01-17T19:08:14 Z blue Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 5632 KB 
#include <iostream>
using namespace std;

using ll = long long;

ll* a;

bool cmp(int i, int j)
{
    if(a[i] != a[j]) return a[i] < a[j];
    else return i < j;
}

const ll INF = 1'000'000'000'000'000'000LL;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

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

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

        ll dp[1+n];
        dp[0] = 0;

        ll mx1 = -INF, mx2 = -INF;

        for(int i = 1; i <= n; i++)
        {
            mx1 = max(mx1, dp[i-1] - a[i]);
            mx2 = max(mx2, dp[i-1] + a[i]);

            dp[i] = max(mx1 + a[i], mx2 - a[i]);
        }

        cout << dp[n] << '\n';
    }
}

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 216 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 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 216 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 35 ms 464 KB Output is correct
8 Correct 31 ms 452 KB Output is correct
9 Correct 32 ms 464 KB Output is correct
10 Correct 30 ms 460 KB Output is correct
11 Correct 31 ms 460 KB Output is correct
12 Correct 31 ms 476 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 216 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 35 ms 464 KB Output is correct
8 Correct 31 ms 452 KB Output is correct
9 Correct 32 ms 464 KB Output is correct
10 Correct 30 ms 460 KB Output is correct
11 Correct 31 ms 460 KB Output is correct
12 Correct 31 ms 476 KB Output is correct
13 Execution timed out 2045 ms 5632 KB Time limit exceeded
14 Halted 0 ms 0 KB -