Submission #152037

#	Time	Username	Problem	Language	Result	Execution time	Memory
152037		souhhcong	Homecoming (BOI18_homecoming)	C++14	0 / 100	261 ms	262148 KiB

homecoming

#include <iostream>
#include <homecoming.h>
using namespace std;

const int N = 2e6+2;
int n, k, a[N], b[N];
long long dp[N], pref[N], ans = 0;

long long get_sum(int l, int r)
{
    if (l <= r)
        return pref[r] - pref[l-1];
    else
        return get_sum(l,n-1) + get_sum(0,r);
}

long long solve(int N, int K, int *A, int *B)
{
    pref[0] = B[0];
    for (int i = 1; i < N; i++)
    {
        pref[i] = pref[i-1] + B[i];
    }
    dp[0] = max(0LL,A[0]-get_sum(0,K-1));
    for (int i = 1; i < N; i++)
    {
        if (i >= K)
            dp[i] = max(dp[i-1] + A[i] - B[(i+K-1)%N], dp[i-K] + A[i] - get_sum(i,(i+K-1)%N));
        else
            dp[i] = dp[i-1] + A[i] - B[(i+K-1)%N];
    }
    for (int i = 0; i < N; i++)
        ans = max(ans,dp[i]);
    //cout << dp[0] << ' ' << dp[1] << ' ' << dp[2] << endl;
    return ans;
}

/*
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    cout << solve(n,k,a,b);
}
*/
/*
3 2
40 80 100
140 0 20
*/

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