oj.uz

Submission #396594

# Submission time Handle Problem Language Result Execution time Memory
396594 2021-04-30T11:23:56 Z nguyen31hoang08minh2003 Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 21236 KB 
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxN = 2e5 + 5;
const ll inf = 1e18;

int n, q, vis[maxN][2];
ll a[maxN], dp[maxN][2];

ll DP(const int idx,
      const bool cut) {
    if (idx >= n)
        return 0;
    if (vis[idx][cut] != q) {
        vis[idx][cut] = q;
        dp[idx][cut] = -inf;
        if (cut) {
            maxi(dp[idx][cut], max(DP(idx + 1, true),
                                   DP(idx + 1, false) + abs(a[idx] - a[idx + 1])));
        } else {
            if (idx == 1 || (a[idx] - a[idx - 1]) * (a[idx + 1] - a[idx]) >= 0)
                maxi(dp[idx][cut], DP(idx + 1, false) + abs(a[idx] - a[idx + 1]));
            maxi(dp[idx][cut], DP(idx + 1, true));
        }
    }
    return dp[idx][cut];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    fort(i, 1, n)
        cin >> a[i];
    memset(vis, -1, sizeof(vis));
    while (q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        fort(i, l, r)
            a[i] += x;
        cout << DP(1, false) << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 3 ms 1868 KB Output is correct
5 Correct 3 ms 1868 KB Output is correct
6 Correct 3 ms 1868 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 3 ms 1868 KB Output is correct
5 Correct 3 ms 1868 KB Output is correct
6 Correct 3 ms 1868 KB Output is correct
7 Correct 337 ms 2264 KB Output is correct
8 Correct 343 ms 2244 KB Output is correct
9 Correct 347 ms 2252 KB Output is correct
10 Correct 346 ms 2244 KB Output is correct
11 Correct 343 ms 2368 KB Output is correct
12 Correct 263 ms 2244 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 3 ms 1868 KB Output is correct
5 Correct 3 ms 1868 KB Output is correct
6 Correct 3 ms 1868 KB Output is correct
7 Correct 337 ms 2264 KB Output is correct
8 Correct 343 ms 2244 KB Output is correct
9 Correct 347 ms 2252 KB Output is correct
10 Correct 346 ms 2244 KB Output is correct
11 Correct 343 ms 2368 KB Output is correct
12 Correct 263 ms 2244 KB Output is correct
13 Execution timed out 2089 ms 21236 KB Time limit exceeded
14 Halted 0 ms 0 KB -