# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
363641 | silverfish | Holiday (IOI14_holiday) | C++14 | 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"
long long dp[3002][3002];
long long int findMaxAttraction(int n, int start, int d, int a[]) {
//dp[i][j] : best score if i visit city i on the jth day
dp[start][1] = a[1];
for(int j = 2; j <= d; ++j){
for(int i = 0; i < n; ++i){
dp[i][j] = 0;
for(int k = 1; k < n; ++k){
if(j-k-1 >= 1){
if(i-k >= 0)
dp[i][j] = max(dp[i][j], a[i] + dp[i-k][j-k-1]);
if(i+k < n)
dp[i][j] = max(dp[i][j], a[i] + dp[i+k][j-k-1]);
}
}
}
}
ll ans = 0;
for(int i = 0; i < n; ++i) ans = max(ans, dp[i][d]);
return ans;
}