제출 #366389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366389		faustaadp	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	2092 ms	2412 KiB

Main

#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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 0 / 55