제출 #629341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629341		MohamedFaresNebili	휴가 (IOI14_holiday)	C++14	7 / 100	49 ms	65240 KiB

holiday

#include <bits/stdc++.h>
 
            using namespace std;
 
            using ll = long long;
            using ld = long double;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            ll DP[1005][1005][2], dp[1005][1005][2];
            ll solve(ll i, ll K, ll add, ll N, ll S, ll D, int C[]) {
                if(i < 0 || i == N || K <= 0) return 0;
                if(DP[i][K][add] != -1) return DP[i][K][add];
                if(add == 0) {
                    ll A = solve(i - 1, K - 1, add, N, S, D, C);
                    ll B = C[i] + solve(i - 1, K - 2, add, N, S, D, C);
                    ll U = solve(S + 1, K - (S - i + 1), 1 - add, N, S, D, C);
                    ll V = C[i] + solve(S + 1, K - (S - i + 1) - 1, 1 - add, N, S, D, C);
                    return DP[i][K][add] = max({A, B, U, V});
                }
                if(add == 1) {
                    ll A = solve(i + 1, K - 1, add, N, S, D, C);
                    ll B = C[i] + solve(i + 1, K - 2, add, N, S, D, C);
                    return DP[i][K][add] = max({A, B});
                }
                return 0;
            }
            ll Solve(ll i, ll K, ll add, ll N, ll S, ll D, int C[]) {
                if(i < 0 || i == N || K <= 0) return 0;
                if(dp[i][K][add] != -1) return dp[i][K][add];
                if(add == 0) {
                    ll A = Solve(i + 1, K - 1, add, N, S, D, C);
                    ll B = C[i] + Solve(i + 1, K - 2, add, N, S, D, C);
                    ll U = Solve(S - 1, K - (i - S + 1), 1 - add, N, S, D, C);
                    ll V = C[i] + Solve(S - 1, K - (i - S + 1) - 1, 1 - add, N, S, D, C);
                    return dp[i][K][add] = max({A, B, U, V});
                }
                if(add == 1) {
                    ll A = Solve(i - 1, K - 1, add, N, S, D, C);
                    ll B = C[i] + Solve(i - 1, K - 2, add, N, S, D, C);
                    return dp[i][K][add] = max({A, B});
                }
                return 0;
            }
 
            ll findMaxAttraction(int N, int start, int D, int attraction[]) {
                memset(DP, -1, sizeof DP);
                memset(dp, -1, sizeof dp);
                ll A = solve(start, D, 0, N, start, D, attraction);
                ll B = Solve(start, D, 0, N, start, D, attraction);
                return max(A, B);
            }

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53