| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 67292 | theknife2001 | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N=3055;
long long dp[N][N*3];
bool vis[N];
int a[N];
int n;
long long bt(int i , int d)
{
if(d==0)
return 0;
// if(dp[i][d]!=-1)
// return dp[i][d];
if(d==1)
{
if(!vis[i])
dp[i][d]=a[i];
else
dp[i][d]=0;
return dp[i][d];
}
long long ret=0;
if(i+1<n)
ret=max(bt(i+1,d-1),ret);
if(i)
ret=max(bt(i-1,d-1),ret);
if(i+1<n&&!vis[i])
{
vis[i]=1;
ret=max(bt(i+1,d-2)+a[i],ret);
vis[i]=0;
}
if(i&&!vis[i])
{
vis[i]=1;
ret=max(bt(i-1,d-2)+a[i],ret);
vis[i]=0;
}
dp[i][d]=ret;
return ret;
}
long long int findMaxAttraction(int m, int start, int d, int ar[])
{
memset(dp,-1,sizeof dp);
n=m;
for(int i=0;i<n;i++)
a[i]=ar[i];
return bt(start,d);
}
int main() {
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}