Submission #1227940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227940		Ghulam_Junaid	Homecoming (BOI18_homecoming)	C++20	0 / 100	89 ms	113736 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][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;
}

// 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