oj.uz

Submission #482781

# Submission time Handle Problem Language Result Execution time Memory
482781 2021-10-26T10:23:02 Z radal Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 74 ms 588 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 72 ms 468 KB Output is correct
8 Correct 72 ms 476 KB Output is correct
9 Correct 74 ms 588 KB Output is correct
10 Correct 71 ms 480 KB Output is correct
11 Correct 69 ms 484 KB Output is correct
12 Correct 57 ms 484 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 72 ms 468 KB Output is correct
8 Correct 72 ms 476 KB Output is correct
9 Correct 74 ms 588 KB Output is correct
10 Correct 71 ms 480 KB Output is correct
11 Correct 69 ms 484 KB Output is correct
12 Correct 57 ms 484 KB Output is correct
13 Runtime error 1 ms 588 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -