제출 #1267562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267562		Alebn	Homecoming (BOI18_homecoming)	C++20	62 / 100	1102 ms	219524 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

int solve(signed n, signed k, signed x[], signed y[]) {
    // put into vectors
    int res = 0;
    vector<int> a(2 * n), b(2 * n), bpref(2 * n);
    for(int i = 0; i < n; i++) {
        a[i] = x[i], b[i] = y[i];
        bpref[i] = (i ? bpref[i - 1] : 0) + b[i];
        res += a[i] - b[i];
    }
    for(int i = n; i < 2 * n; i++) {
        a[i] = a[i - n], b[i] = b[i - n];
        bpref[i] = bpref[i - 1] + b[i];
    }
    // dp setup
    vector<vector<int>> dp(n + 1, vector<int>(2, LONG_MIN));
    res = max(res, 0LL);
    // first case
    // bug when tries to take everything, but doesn't matter since always worse than res above
    dp[0][1] = 0;
    for(int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        if(dp[i - 1][1] != LONG_MIN) dp[i][1] = max(dp[i][1], dp[i - 1][1] + a[i - 1] - b[i + k - 2]);
        if(dp[i - 1][0] != LONG_MIN) dp[i][1] = max(dp[i][1], dp[i - 1][0] + a[i - 1] - bpref[i + k - 2] + (i > 1 ? bpref[i - 2] : 0));
    }
    res = max(res, dp[n][1]);
    // second case
    int end;
    for(int x = 1; x <= k + 1; x++) {
        for(int i = 0; i <= n; i++) dp[i] = {LONG_MIN, LONG_MIN};
        dp[x - 1] = {0, LONG_MIN}, end = n + x - k - 1;
        for(int i = x; i <= end; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            if(dp[i - 1][1] != LONG_MIN) dp[i][1] = max(dp[i][1], dp[i - 1][1] + a[i - 1] - b[i + k - 2]);
            if(dp[i - 1][0] != LONG_MIN) dp[i][1] = max(dp[i][1], dp[i - 1][0] + a[i - 1] - bpref[i + k - 2] + (i > 1 ? bpref[i - 2] : 0));
        }
        res = max(res, max(dp[end][0], dp[end][1]));
    }
    return res;
}

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