Submission #152069

#	Time	Username	Problem	Language	Result	Execution time	Memory
152069		souhhcong	Homecoming (BOI18_homecoming)	C++14	0 / 100	53 ms	14080 KiB

homecoming

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

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

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

long long int 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,N));
    for (int i = 1; i < N; i++)
    {
        if (i >= K)
            dp[i] = max(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, N)));
        else
            dp[i] = max(dp[i], dp[i-1] + A[i] - B[(i+K-1)%N]);
    }
    for (int i = 0; i < N; i++)
    {
        dp[i] = max(dp[i], max(dp[(i-1+N)%N] + A[i] - B[(i+K-1)%N], dp[(i-K+N)%N] + A[i] - get_sum(i,(i+K-1)%N, 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