oj.uz

Submission #867980

# Submission time Handle Problem Language Result Execution time Memory
867980 2023-10-30T02:44:17 Z ComGa999ms Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 8948 KB 
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define repd(i, r, l) for (int i = r; i >= l; --i)
#define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin());
#define sz(v) (int)(v).size()
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mp make_pair
#define eps double(1e-9)
#define vii vector<int>
#define pii pair<int,int>
#define p2i pair<int,pii>
#define endl '\n'

using namespace std;

const int N = 1e6 + 5;
const int MN = 2e3 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18 + 7;
const bool Emily = false;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {
    return l+rng()%(r-l+1);
}

bool minimize(int &a, int b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

bool maximize(int &a, int b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

int n, q;
int a[N], dp[N];
int temp1, temp2;

void solve(void) {
    cin >> n >> q;
    rep(i, 1, n) cin >> a[i];
    while (q--) {
        int l, r, x;
        cin>> l >> r >> x;
        rep(i, l, r) a[i] += x;

        temp1 = temp2 = -inf;
        rep(i, 1, n) {
            maximize(temp1, dp[i - 1] - a[i]);
            maximize(temp2, dp[i - 1] + a[i]);
            dp[i] = max(temp1 + a[i], temp2 - a[i]);
        }
        cout << dp[n] << endl;
    }
}

signed main()
{
    #define task "RECIPE"
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    if (Emily) {
        int t; cin >> t;
        while (t-- ) solve();
    } else solve();

    return 0;
}

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 2392 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 2392 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 34 ms 2648 KB Output is correct
8 Correct 35 ms 2652 KB Output is correct
9 Correct 35 ms 2652 KB Output is correct
10 Correct 35 ms 2648 KB Output is correct
11 Correct 34 ms 2532 KB Output is correct
12 Correct 34 ms 2640 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 2392 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 34 ms 2648 KB Output is correct
8 Correct 35 ms 2652 KB Output is correct
9 Correct 35 ms 2652 KB Output is correct
10 Correct 35 ms 2648 KB Output is correct
11 Correct 34 ms 2532 KB Output is correct
12 Correct 34 ms 2640 KB Output is correct
13 Execution timed out 2040 ms 8948 KB Time limit exceeded
14 Halted 0 ms 0 KB -