oj.uz

Submission #1070326

# Submission time Handle Problem Language Result Execution time Memory
1070326 2024-08-22T13:13:11 Z VMaksimoski008 Sjeckanje (COCI21_sjeckanje) C++17
15 / 110
 2000 ms 596 KB 
#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

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

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

    vector<ll> v(n+1), dp(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];

    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        for(int i=l; i<=r; i++) v[i] += x;

        for(int i=2; i<=n; i++) {
            dp[i] = 0;
            ll mn=1e18, mx=-1e18;
            bool t = (v[i-1] >= v[i]);
            for(int j=i; j>=1; j--) {
                if(t == 1 && j < i && v[j] < v[i]) break;
                if(t == 0 && j < i && v[j] > v[i]) break;
                mn = min(mn, v[j]);
                mx = max(mx, v[j]);
                dp[i] = max(dp[i], dp[j-1] + mx - mn);
            }
        }

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

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1151 ms 496 KB Output is correct
8 Correct 902 ms 596 KB Output is correct
9 Correct 833 ms 592 KB Output is correct
10 Correct 732 ms 588 KB Output is correct
11 Correct 1049 ms 560 KB Output is correct
12 Execution timed out 2052 ms 572 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1151 ms 496 KB Output is correct
8 Correct 902 ms 596 KB Output is correct
9 Correct 833 ms 592 KB Output is correct
10 Correct 732 ms 588 KB Output is correct
11 Correct 1049 ms 560 KB Output is correct
12 Execution timed out 2052 ms 572 KB Time limit exceeded
13 Halted 0 ms 0 KB -