Submission #1228265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228265		Ghulam_Junaid	Homecoming (BOI18_homecoming)	C++20	31 / 100	1097 ms	28172 KiB

homecoming

#include <bits/stdc++.h>
// #include "homecoming.h"
using namespace std;

typedef long long ll;

ll solve(int n, int k, int *a, int *b){
    ll dp[2 * n + 10] = {};
    ll pa[2 * n + 10], pb[2 * n + 10];
    
    pa[0] = pb[0] = 0;
    for (int i = 1; i <= 2 * n; i ++){
        pa[i] = pa[i - 1] + a[(i - 1) % n];
        pb[i] = pb[i - 1] + b[(i - 1) % n];
    }

    ll ans = pa[n] - pb[n];
    for (int i = 1; i <= n; i ++){
        memset(dp, 0, sizeof dp);
        ll mx = -1e18;
        for (int j = i + 1; j < i + n; j ++){
            dp[j] = dp[j - 1];
            ans = max(ans, dp[j]);
            if (j - k < i) continue;
            mx = max(mx, dp[j - k] - pa[j - k] + pb[j - k]);
            ll val = pa[j - k + 1] - pb[j];
            dp[j] = max(dp[j], mx + val);
            ans = max(ans, dp[j]);
        }
    }
    ans = max(ans, 0ll);
    return ans;
}

// int main(){
//     int n = 5, k = 3;
//     int a[n] = {10, 6, 2, 1, 1};
//     int b[n] = {4, 3, 5, 2, 10};
//     cout << solve(n, k, a, b) << endl;
// }

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