题解 | 秘藏

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    long long* a = (long long*)malloc((n + 1) * sizeof(long long));
    long long* b = (long long*)malloc((n + 1) * sizeof(long long));

    // 读取表世界金币，索引从1开始
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    // 读取里世界金币，索引从1开始
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
    }

    // dpA[i]: 到达表世界i号点的最大金币
    // dpB[i]: 到达里世界i号点的最大金币
    long long* dpA = (long long*)malloc((n + 1) * sizeof(long long));
    long long* dpB = (long long*)malloc((n + 1) * sizeof(long long));

    // 初始化
    dpA[1] = a[1];  // 起点在表世界1号点
    dpB[1] = -1e18; // 里世界1号点初始不可达

    for (int i = 1; i < n; i++) {
        // 从表世界i到表世界i+1（直接走）
        dpA[i + 1] = dpA[i] + a[i + 1];

        // 从里世界i到表世界i+1（需要跃迁）
        if (dpB[i] >= k) {
            dpA[i + 1] = max(dpA[i + 1], dpB[i] - k + a[i + 1]);
        }

        // 从里世界i到里世界i+1（直接走）
        dpB[i + 1] = dpB[i] + b[i + 1];

        // 从表世界i到里世界i+1（需要跃迁）
        if (dpA[i] >= k) {
            dpB[i + 1] = max(dpB[i + 1], dpA[i] - k + b[i + 1]);
        }
    }

    // 最终结果取到达n号点的最大值
    long long result = max(dpA[n], dpB[n]);
    printf("%lld\n", result);

    free(a);
    free(b);
    free(dpA);
    free(dpB);
    return 0;
}