Submission #482781

#	Time	Username	Problem	Language	Result	Execution time	Memory
482781		radal	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	74 ms	588 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 3e3+20,mod = 1e9+7,inf = 1e9,sq = 65;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
ll a[N],dp[N];
int L[N][2];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    rep(i,0,n) cin >> a[i];
    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        l--;
        rep(i,l,r) a[i] += x;
        L[0][0] = 0;
        L[0][1] = 0;
        rep(i,1,n){
            if (a[i] > a[i-1]){
                L[i][1] = L[i-1][1];
                L[i][0] = i;
            }
            if (a[i] == a[i-1]){
                L[i][1] = i;
                L[i][0] = i;
            }
            if (a[i] < a[i-1]){
                L[i][0] = L[i-1][0];
                L[i][1] = i;
            }
        }
        rep(i,1,n){
            dp[i] = max(dp[L[i][0]-1]+a[L[i][0]]-a[i],dp[L[i][1]-1]-a[L[i][1]]+a[i]);
            if (L[i][0] != i)
                dp[i] = max(dp[i],dp[L[i][0]]+a[L[i][0]+1]-a[i]);
            else if(L[i][1] != i)
                dp[i] = max(dp[i],dp[L[i][1]]-a[L[i][1]+1]+a[i]);
        }
        cout << dp[n-1] << endl;
    }
}

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