제출 #422734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422734		egekabas	Homecoming (BOI18_homecoming)	C++14	31 / 100	383 ms	262148 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
long long solve(int N, int K, int *A, int *B){
    vector<ll> pre(2*N);
    for(ll i = 0; i < 2*N; ++i){
        pre[i] = B[i%N];
        if(i)
            pre[i] += pre[i-1];
    }
    vector<vector<ll>> dp(N, vector<ll>(2, -1e18));
    ll ans = 0;

    dp[0][1] = A[0]-pre[K-1];
    for(int i = 1; i < N; ++i){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = dp[i-1][0]+A[i]-pre[min(i+K-1, N-1)]+pre[i-1];
        if(i+K-1 < N)
            dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]-B[i+K-1]);
        else
            dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]);
        dp[i][1] = max((ll)-1e18, dp[i][1]);
    }
    ans = max({ans, dp[N-1][0], dp[N-1][1]});

    dp = vector<vector<ll>>(N, vector<ll>(2, -1e18));
    dp[0][0] = 0;
    for(int i = 1; i < N; ++i){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        
        dp[i][1] = dp[i-1][0]+A[i]-pre[i+K-1]+pre[i-1];
        dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]-B[(i+K-1)%N]);
        
        dp[i][1] = max((ll)-1e18, dp[i][1]);
    }
    ans = max({ans, dp[N-1][0], dp[N-1][1]});
    return ans;

}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38