oj.uz

답안 #1070326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070326 2024-08-22T13:13:11 Z VMaksimoski008 Sjeckanje (COCI21_sjeckanje) C++17
15 / 110
 2000 ms 596 KB 
#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

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

    int n, q;
    cin >> n >> q;

    vector<ll> v(n+1), dp(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];

    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        for(int i=l; i<=r; i++) v[i] += x;

        for(int i=2; i<=n; i++) {
            dp[i] = 0;
            ll mn=1e18, mx=-1e18;
            bool t = (v[i-1] >= v[i]);
            for(int j=i; j>=1; j--) {
                if(t == 1 && j < i && v[j] < v[i]) break;
                if(t == 0 && j < i && v[j] > v[i]) break;
                mn = min(mn, v[j]);
                mx = max(mx, v[j]);
                dp[i] = max(dp[i], dp[j-1] + mx - mn);
            }
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1151 ms 496 KB Output is correct
8 Correct 902 ms 596 KB Output is correct
9 Correct 833 ms 592 KB Output is correct
10 Correct 732 ms 588 KB Output is correct
11 Correct 1049 ms 560 KB Output is correct
12 Execution timed out 2052 ms 572 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1151 ms 496 KB Output is correct
8 Correct 902 ms 596 KB Output is correct
9 Correct 833 ms 592 KB Output is correct
10 Correct 732 ms 588 KB Output is correct
11 Correct 1049 ms 560 KB Output is correct
12 Execution timed out 2052 ms 572 KB Time limit exceeded
13 Halted 0 ms 0 KB -