Submission #1228000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228000		Ghulam_Junaid	Homecoming (BOI18_homecoming)	C++20	0 / 100	1095 ms	27716 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 ++){
        dp[i] = 0;
        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[i - k + 1] - pb[i];
            dp[j] = max(dp[j], mx + val);
            ans = max(ans, dp[j]);
        }
    }
    ans = max(ans, 0ll);
    return ans;
}

// int main(){
//     int a[3] = {40, 80, 100};
//     int b[3] = {140, 0, 20};
//     cout << solve(3, 2, a, b) << endl;
// }

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