Submission #1167799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167799		sunflower	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	43 ms	1864 KiB

Main

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cout << #x << " = " << (x) << endl

#define left    __left
#define right   __right
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int n, q;

const long long INF = (long long) 1e18 + 7;

#define MAX_N 200'200
ll a[MAX_N + 2];

namespace subtask1 {
    bool check() {
        return (n <= 200 && q <= 200);
    }

    ll dp[202];

    void solve() {
        while (q--) {
            int L, R, addVal;
            cin >> L >> R >> addVal;
            FOR(i, L, R) a[i] += addVal;

            FOR(i, 1, n) dp[i] = -INF;

            dp[0] = 0;
            FOR(i, 1, n) {
                ll ma = -INF, mi = INF;
                FORD(j, i, 1) {
                    maximize(ma, a[j]);
                    minimize(mi, a[j]);

                    maximize(dp[i], dp[j - 1] + ma - mi);
                }
            }

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

namespace subtask2 {
    bool check() {
        return (n <= 3000 && q <= 3000);
    }

    int len[3030][2];
    ll dp[3030];

    // 0: increase;
    // 1: decrease;

    void prepare() {
        len[1][0] = len[1][1] = 0;
        FOR(i, 2, n) {
            len[i][0] = len[i][1] = 0;

            if (a[i] == a[i - 1]) {
                if (len[i - 1][0] || i == 2) len[i][0] = len[i - 1][0] + 1;
                if (len[i - 1][1] || i == 2) len[i][1] = len[i - 1][1] + 1;
            } else if (a[i] > a[i - 1]) {
                len[i][0] = len[i - 1][0] + 1;
            } else {
                len[i][1] = len[i - 1][1] + 1;
            }
        }
    }

    // [nxet: dap an toi uu la 1 doan tang dan or giam dan]
    // prove: [max...min] or [min...max];

    void solve() {
        while (q--) {
            int L, R, addVal;
            cin >> L >> R >> addVal;
            FOR(i, L, R) a[i] += addVal;

            prepare();
            FOR(i, 1, n) dp[i] = -INF;

            dp[0] = 0;
            FOR(i, 1, n) {
                dp[i] = dp[i - 1];
                int length = max(len[i][0], len[i][1]) + 1;
                maximize(dp[i], dp[i - length] + abs(a[i] - a[i - length + 1]));
                if (i - length + 2 <= i)
                    maximize(dp[i], dp[i - length + 1] + abs(a[i] - a[i - length + 2]));
            }

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

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("test.inp","r",stdin);
    // freopen("test.out","w",stdout);
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];

//    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    if (subtask2 :: check()) return subtask2 :: solve(), 0;

    return 0;
}

/* Discipline and Calm */

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 0 / 55