Submission #1138092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138092		poat	Homecoming (BOI18_homecoming)	C++17	100 / 100	228 ms	203912 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

#define INF 2e18
#define MOD 1e9+7


long long solve(int N, int K, int *A, int *B){
    ll n=N, k=K;
    vector<ll> a(n+1), b(2*n+1), pref(2*n+1);
    vector<vector<ll>> dp(n+1, vector<ll>(2));
    for (ll i=1; i<=n; i++) a[i]=A[i-1];
    for (ll i=1; i<=n; i++) {b[i]=B[i-1]; pref[i]=pref[i-1]+b[i];}
    for (ll i=n+1; i<=2*n; i++) pref[i]=pref[i-1];
    ll res; res=dp[1][0] = dp[1][1] = a[1]-pref[k];
    for (ll i=2; i<=n; i++){
        dp[i][1]=max(dp[i-1][1]-b[i+k-1], dp[i-1][0]-pref[i+k-1]+pref[i-1])+a[i];
        dp[i][0]=max(dp[i-1][1], dp[i-1][0]);
    }
    res=max({res, dp[n][0], dp[n][1]});
    for (ll i=n+1; i<=2*n; i++) {b[i] = b[i-n]; pref[i]=pref[i-1]+b[i];}
    dp[1][0] = 0;
    dp[1][1] = a[1]-pref[k];
    for (ll i=2; i<=n; i++){
        dp[i][1]=max(dp[i-1][1]-b[i+k-1], dp[i-1][0]-pref[i+k-1]+pref[i-1])+a[i];
        dp[i][0]=max(dp[i-1][1], dp[i-1][0]);
    }
    res=max({res, dp[n][1], dp[n][0]});
    return res;
}

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