제출 #969628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969628		vjudge1	메기 농장 (IOI22_fish)	C++17	52 / 100	1117 ms	2097152 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<int64_t>> pref(N, vector<int64_t>(N + 1));
    vector<vector<int>> a(N, vector<int>(N));

    for (int i = 0; i < M; i++) {
        a[X[i]][Y[i]] = W[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) pref[i][j + 1] = pref[i][j] + a[i][j];
    }
    const int64_t inf = 1e18;
    vector<vector<int64_t>> dp(N + 1, vector<int64_t>(2, -inf));
    dp[0][0] = 0;
    dp[N][1] = 0;
    for (int i = 0; i < N; i++) {
        vector<vector<int64_t>> ndp(N + 1, vector<int64_t>(2, -inf));
        if (i + 1 < N) {
            for (int j = 0; j < N; j++) {
                dp[j + 1][0] = max(dp[j + 1][0], dp[j][0] + a[i][j]);
            }
        }
        for (int j = N - 1; j > 0; j--) {
            dp[j - 1][1] = max(dp[j - 1][1], dp[j][1] + a[i][j - 1]);
        }
        if (i == 1) dp[0][0] = max(dp[0][0], pref[0][N]);
        if (i + 2 < N) dp[0][0] = max(dp[0][0], dp[0][1]);
        if (i == N - 1) break;
        for (int j = 0; j <= N; j++) {
            ndp[j][0] = max(ndp[j][0], dp[j][0]);
            if (j == N) ndp[N][1] = max(ndp[N][1], dp[j][0]);
            if (j == 0) ndp[N][1] = max(ndp[N][1], dp[j][0]);
            if (j == 0 && i + 1 == N - 1) ndp[N][0] = max(ndp[N][0], dp[0][0] + pref[N - 1][N]);
        }
        for (int j = 0; j <= N; j++) {
            ndp[j][1] = max(ndp[j][1], dp[j][1]);
            if (j == N) ndp[N - 1][1] = max(ndp[N - 1][1], dp[j][1] + a[i + 1][N - 1]);
            if (i + 2 < N && j == 0) ndp[0][0] = max(ndp[0][0], dp[j][1]);
            if (j == 0) ndp[0][0] = max(ndp[0][0], dp[j][1]);
        }
        ndp.swap(dp);
    }

    return max(dp[0][1], max(dp[N][0], dp[N][1]));
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16