# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
469670 | MohamedFaresNebili | 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 <bits/stdc++.h>
#include"holiday.h"
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()
const ll MOD = 998244353;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const int nx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
const int ny[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
bool vis[100005]; ll dp[]
long long int solve(int i, int d, int n, int arr[]) {
if(d==0) return 0;
long long best;
if(i==0) {
if(vis[i]) best=solve(i+1, d-1, n, arr);
else {
ll a=solve(i+1, d-1, n, arr);
vis[i]=1; ll b=arr[i]+solve(i, d-1, n, arr); vis[i]=0;
best=max(a, b);
}
return best;
}
if(i==n-1) {
if(vis[i]) best=solve(i-1, d-1, n, arr);
else {
ll a=solve(i-1, d-1, n, arr);
vis[i]=1; ll b=arr[i]+solve(i, d-1, n, arr); vis[i]=0;
best=max(a, b);
}
return best;
}
if(vis[i]) best=max(solve(i-1, d-1, n, arr), solve(i+1, d-1, n, arr));
else {
ll a=max(solve(i+1, d-1, n, arr), solve(i-1, d-1, n, arr));
vis[i]=1; ll b=arr[i]+solve(i, d-1, n, arr); vis[i]=0;
best=max(a, b);
}
return best;
}
long long int findMaxAttraction(int n, int start, int d, int arr[]) {
memset(vis, false, sizeof vis);
return solve(start, d, n, arr);
}