Codeforces-Solutions-B/Array Walk.cpp at master · devKiam/Codeforces-Solutions-B · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long ull;
using namespace std;

ll mz[100000][5];

ll aw(vector<ll> &v, ll k, ll z, ll i)
{
    ll result;
    bool flag = false;

    if(k==0)
    {
        return v[i];
    }

    if(mz[i][z]!=-1)
    {
        return mz[i][z];
    }

    if(k>0)
    {
        if(z!=0 && flag == false && i>0){
            flag = true;
            result = max( v[i] + aw(v, k-1, z-1, i-1), v[i] + aw(v, k-1, z, i+1) );
        }
        else
        {
            flag = false;
            result = v[i] + aw(v, k-1, z, i+1);
        }
    }

    mz[i][z] = result;
    return result;

}

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

    ll t; cin>>t;
    for(int tc=1; tc<=t; tc++)
    {
        ll n,k,z; cin>>n>>k>>z;
        k--;
        vector<ll> v;
        for(int i=0; i<n; i++)
        {
            ll input; cin>>input;
            v.push_back(input);
        }

        memset(mz, -1, sizeof(mz));
        cout<<aw(v, k, z, 1) + v[0]<<"\n";
    }
}