Submission #396594

#	Time	Username	Problem	Language	Result	Execution time	Memory
396594		nguyen31hoang08minh2003	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	2089 ms	21236 KiB

Main

#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxN = 2e5 + 5;
const ll inf = 1e18;

int n, q, vis[maxN][2];
ll a[maxN], dp[maxN][2];

ll DP(const int idx,
      const bool cut) {
    if (idx >= n)
        return 0;
    if (vis[idx][cut] != q) {
        vis[idx][cut] = q;
        dp[idx][cut] = -inf;
        if (cut) {
            maxi(dp[idx][cut], max(DP(idx + 1, true),
                                   DP(idx + 1, false) + abs(a[idx] - a[idx + 1])));
        } else {
            if (idx == 1 || (a[idx] - a[idx - 1]) * (a[idx + 1] - a[idx]) >= 0)
                maxi(dp[idx][cut], DP(idx + 1, false) + abs(a[idx] - a[idx + 1]));
            maxi(dp[idx][cut], DP(idx + 1, true));
        }
    }
    return dp[idx][cut];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    fort(i, 1, n)
        cin >> a[i];
    memset(vis, -1, sizeof(vis));
    while (q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        fort(i, l, r)
            a[i] += x;
        cout << DP(1, false) << '\n';
    }
    return 0;
}

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