Submission #1227932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227932		Ghulam_Junaid	Homecoming (BOI18_homecoming)	C++20	0 / 100	73 ms	113984 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 + 5][k + 10];
    
    for (int i = 0; i < 2 * n + 10; i ++)
        for (int j = 0; j < k + 10; j ++)
            dp[i][j] = -1e18;

    ll ans = 0;
    for (int i = 0; i < n; i ++)
        ans += a[i] - b[i];
    dp[0][0] = dp[0][1] = 0;
    for (int i = 1; i <= 2 * n; i ++){
        for (int j = 0; j <= k; j ++){
            dp[i][j] = max(dp[i - 1][j + 1], dp[i - 1][j] - a[(i + j - 1) % n]) + b[(i - 1) % n] * (j == k);
            ans = max(ans, dp[i][j]);
        }
    }
    return ans;
}

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