oj.uz

Submission #950286

# Submission time Handle Problem Language Result Execution time Memory
950286 2024-03-20T07:42:11 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 8056 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long



int f(vector<int> &a){
    int n = a.size();
    vector<int> dp(n);
    dp[0] = 0;
    int minus = -a[0], plus = a[0];
    for(int i = 1;i < n; i++){
        minus = max(dp[i-1] - a[i], minus);
        plus = max(dp[i-1] + a[i], plus);
        dp[i] = max({dp[i-1], plus - a[i], minus + a[i]});
    }
    return *max_element(all(dp));
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(auto &e : a) cin >> e;
    while(q--){
        int l, r, x; cin >> l >> r >> x;
        l--, r--;
        vector<int> v;
        for(int i = 0;i < n; i++){
            if(l <= i && r >= i) a[i]+= x;
            if(v.size() >= 2 && a[i] == v[v.size()-1] && a[i] == v[v.size()-2]){
                continue;
            }
            v.push_back(a[i]);
        }
       
        cout << f(v) << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 472 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 472 KB Output is correct
7 Correct 70 ms 624 KB Output is correct
8 Correct 66 ms 600 KB Output is correct
9 Correct 64 ms 600 KB Output is correct
10 Correct 71 ms 632 KB Output is correct
11 Correct 72 ms 644 KB Output is correct
12 Correct 76 ms 636 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 472 KB Output is correct
7 Correct 70 ms 624 KB Output is correct
8 Correct 66 ms 600 KB Output is correct
9 Correct 64 ms 600 KB Output is correct
10 Correct 71 ms 632 KB Output is correct
11 Correct 72 ms 644 KB Output is correct
12 Correct 76 ms 636 KB Output is correct
13 Execution timed out 2048 ms 8056 KB Time limit exceeded
14 Halted 0 ms 0 KB -