oj.uz

Submission #932546

# Submission time Handle Problem Language Result Execution time Memory
932546 2024-02-23T15:29:39 Z a_l_i_r_e_z_a Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 39 ms 648 KB 
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 3000 + 5;
const int inf = 1e9 + 7;
ll n, q, a[maxn], dp[maxn], b[maxn];

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

    cin >> n >> q;
    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;
        dp[1] = 0;
        dp[2] = abs(a[2] - a[1]);
        b[2] = 1;  
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1];
            if((a[i] >= a[i - 1]) == (a[i - 1] >= a[i - 2])) b[i] = b[i - 1];
            else b[i] = i - 1;
            smax(dp[i], abs(a[i] - a[b[i]]) + dp[b[i] - 1]);
            smax(dp[i], abs(a[i] - a[b[i] + 1]) + dp[b[i]]);
        }
        cout << dp[n] << '\n';
    }

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 32 ms 648 KB Output is correct
8 Correct 39 ms 632 KB Output is correct
9 Correct 35 ms 604 KB Output is correct
10 Correct 33 ms 636 KB Output is correct
11 Correct 33 ms 644 KB Output is correct
12 Correct 35 ms 604 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 32 ms 648 KB Output is correct
8 Correct 39 ms 632 KB Output is correct
9 Correct 35 ms 604 KB Output is correct
10 Correct 33 ms 636 KB Output is correct
11 Correct 33 ms 644 KB Output is correct
12 Correct 35 ms 604 KB Output is correct
13 Runtime error 1 ms 608 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -