oj.uz

Submission #366389

# Submission time Handle Problem Language Result Execution time Memory
366389 2021-02-14T06:28:06 Z faustaadp Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 2412 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 1e6 + 5;
const int mo = 1e9 + 7;
const ld eps = 1e-9;
ll n, q, a[NN], d[3030][4], x[3030][3030];
ll depe(ll pos, ll tr)
{
    if(pos > n && tr == 0)
        return 0;
    if(pos > n)
        return -1e18;
    ll &ret = d[pos][tr];
    if(ret == -1)
    {
        ret = depe(pos + 1, tr);
        if(tr == 0)
        {
            ret = max(ret, depe(pos + 1, 1) + a[pos]);
            ret = max(ret, depe(pos + 1, 2) - a[pos]);
        }
        else
        if(tr == 1)
            ret = max(ret, depe(pos + 1, 0) - a[pos]);
        else
            ret = max(ret, depe(pos + 1, 0) + a[pos]);
    } 
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> q ;
    for(ll i = 1; i <= n; i++)
        cin >> a[i];
    for(ll i = 1; i <= q; i++)
    {
        ll L, R, tam;
        cin >> L >> R >> tam;
        for(ll i = L; i <= R; i++)
            a[i] += tam;
        memset(d, -1, sizeof(d));
        cout << depe(1, 0) << "\n";
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 343 ms 712 KB Output is correct
8 Correct 364 ms 844 KB Output is correct
9 Correct 341 ms 748 KB Output is correct
10 Correct 357 ms 876 KB Output is correct
11 Correct 341 ms 748 KB Output is correct
12 Correct 344 ms 748 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 343 ms 712 KB Output is correct
8 Correct 364 ms 844 KB Output is correct
9 Correct 341 ms 748 KB Output is correct
10 Correct 357 ms 876 KB Output is correct
11 Correct 341 ms 748 KB Output is correct
12 Correct 344 ms 748 KB Output is correct
13 Execution timed out 2092 ms 2412 KB Time limit exceeded
14 Halted 0 ms 0 KB -