Submission #1152488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152488		simuyu	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	648 ms	1788 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second

ll N, Q;
ll a[3005], d[3005];

map<ll, ll> memo[3005];

// at each place, can either continue, or take abs and conclude (and ignore next d)
ll dp(ll idx, ll currval) {
    //cout << "DP(" << idx << ',' << currval << ')';
    if (idx >= N) {
        //cout << " = 0" << endl;
        return 0;
    }
    if (idx==N-1) {
        // js abs and conclude
        //cout << " = " << abs(currval+d[idx]) << endl;
        return max(abs(currval), abs(currval+d[idx]));
    }

    // two options, continue or conclude (concluding is also skipping next one)
    //return max( dp(idx+1, currval+d[idx]) , abs(currval+d[idx]) + dp(idx+2, 0) );
    //ll t = max( dp(idx+1, currval+d[idx]) , abs(currval+d[idx]) + dp(idx+2, 0) );
    //cout << " = " << t;
    //return t;


    if (!memo[idx][currval]) {
        memo[idx][currval] = max( dp(idx+1, currval+d[idx]) , abs(currval+d[idx]) + dp(idx+2, 0) );
    }
    return memo[idx][currval];
}


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

    cin >> N >> Q;

    d[0] = 0;
    cin >> a[0];

    for (ll i=1; i<N; i++) {
        cin >> a[i];
        d[i] = a[i] - a[i-1];
    }


    // handle queries
    ll s, e, v;
    for (ll q=0; q<Q; q++) {
        cin >> s >> e >> v;
        d[s-1] += v;
        d[e] -= v;

        // now solve with DP
        /*cout << "D: ";
        for (int i=1; i<N; i++) cout << d[i] << ' ';
        cout << endl;*/

        for (ll i=0; i<N; i++) {
            memo[i].clear();
        }

        cout << dp(1, 0) << endl;
    }



    return 0;
}

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