Submission #1099260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099260		Phuoc	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	348 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define el '\n';
#define ll long long
#define fi first
#define se second
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))

template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b) {a = b; return true;} return false;
    }

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if(a < b) {a = b; return true;} return false;
    }

const int MOD = (int)1e9 + 7;

template <class T1, class T2> 
    void add (T1 &a, T2 b) {
        a += b;
        if (a >= MOD) a -= MOD;
    }

const int N = 200100;
const int oo = (int)1e9 + 7;
const ll INF = (ll)1e18 + 9LL;
const int LOG = 22;

int n, q;
long long a[N];

void init (void) { 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
}

namespace subtask1 {
    long long mi[222][222], ma[222][222];
    long long dp[222];

    void solve (void) {
        while(q--) {
            int l, r, x; cin >> l >> r >> x;
            for (int i = l; i <= r; i++) a[i] += x;
            for (int i = 1; i <= n; i++) {
                mi[i][i] = a[i];
                ma[i][i] = a[i];
                for (int j = i + 1; j <= n; j++) {
                    mi[i][j] = min(mi[i][j - 1], 1LL * a[j]);
                    ma[i][j] = max(ma[i][j - 1], 1LL * a[j]);
                }
            }

            for (int i = 1; i <= n; i++) {
                dp[i] = ma[1][i] - mi[1][i];
                // cout << dp[i] << el;
                for (int j = 0; j < i; j++) {
                    maximize(dp[i], dp[j] + 1LL * ma[j + 1][i] - 1LL * mi[j + 1][i]);
                }
            }
            cout << dp[n] << el;
        }

    }
}

namespace subtask2 {
    long long dp[3333];
    int diff[3333], pre[3333];

    void solve (void) {
        while(q--) {
            bool isMonotonous = true;
            int l, r, x; cin >> l >> r >> x;
            for (int i = l; i <= r; i++) a[i] += x;
            bool mark = ((a[2] - a[1]) > 0);
            for (int i = 3; i <= n; i++) {
                if(a[i] == a[i - 1]) continue;
                bool t = ((a[i] - a[i - 1]) > 0);
                if(mark != t) {
                    isMonotonous = false;
                    break;
                }
            }
            if(!isMonotonous) {
                int cur_min = a[1], cur_max = a[1];
                vector <int> pre (n + 1, 0), suf (n + 1, 0);
                for (int i = 1; i <= n; i++) {
                    maximize(cur_max, a[i]);
                    minimize(cur_min, a[i]);
                    pre[i] = cur_max - cur_min;
                }
                cur_min = a[n], cur_max = a[n];
                for (int i = n; i >= 1; i--) {
                    maximize(cur_max, a[i]);
                    minimize(cur_min, a[i]);
                    suf[i] = cur_max - cur_min;
                }
                long long ans = 0;
                for (int i = 1; i < n; i++) {
                    maximize(ans, pre[i] + suf[i + 1]);
                }
                cout << ans << el;
            }
            else {
                for (int i = 1; i < n; i++) diff[i] = a[i] - a[i + 1];
                for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + diff[i];
                for (int i = 1; i < n; i++) {
                    dp[i] = dp[i - 1];
                    maximize(dp[i], dp[i - 2] + diff[i]);
                }
                cout << dp[n];
            }
        }
    }
}

void solve (void) {
    subtask2::solve();
}

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

    int ntest = 1; 

    while(ntest--) {
        init();
        solve();
    }
    return 0;
}

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