제출 #1260960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260960		rayan_bd	메기 농장 (IOI22_fish)	C++20	0 / 100	31 ms	7200 KiB

fish

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

using ll = long long;
const int MAXN = 305;

// dp[i][j][0] = best using columns 1..i, with column i "blocked" up to height j (pier length j)
// dp[i][j][1] = best using columns 1..i, taking fish in column i from bottom..j (caught by left neighbor)
// dp[i][j][2] = best using columns 1..i, taking fish in column i bottom..j and also some in column i-1
static ll dp[MAXN][MAXN][3];
static ll cost[MAXN][MAXN]; // cost[c][h] = sum of weights in column c up to height h (prefix)

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    // reset
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) {
            cost[i][j] = 0;
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 0;
        }
    }

    // collect fish per column and build prefix sums per column
    vector<vector<pair<int,int>>> col(N+1);
    for (int t = 0; t < M; ++t) {
        int c = X[t] + 1;     // 1-index columns
        int r = Y[t] + 1;     // 1-index rows
        col[c].push_back({r, W[t]});
    }
    for (int c = 1; c <= N; ++c) {
        sort(col[c].begin(), col[c].end());
        int p = 0;
        for (int h = 1; h <= N; ++h) {
            cost[c][h] = cost[c][h-1];
            while (p < (int)col[c].size() && col[c][p].first == h) {
                cost[c][h] += col[c][p].second;
                ++p;
            }
        }
    }

    auto range_sum = [&](int c, int l, int r) -> ll {
        if (l > r) return 0;
        return cost[c][r] - cost[c][l-1];
    };

    // IMPORTANT: start from i = 2 so column 1 never "catches" from a non-existent left pier
    for (int i = 2; i <= N; ++i) {
        // --- dp[i][j][2]: take in col i (up to j) and also some in col i-1 ---
        // For a chosen left pier height k at col (i-1):
        // - col i contributes cost[i][min(j,k)]  (left pier must reach that row)
        // - col i-1 contributes range (k, j]     (own pier doesn't cover, right pier j catches)
        // dp contribution from col <= i-2 is independent of k -> take best0 = max_t dp[i-2][t][0]
        ll best0 = 0;
        if (i >= 2) {
            for (int t = 0; t <= N; ++t) best0 = max(best0, dp[i-2][t][0]);
        }
        for (int j = 0; j <= N; ++j) {
            ll best_k = 0; // we maximize over k
            for (int k = 0; k <= N; ++k) {
                ll take_i   = cost[i][min(j, k)];
                ll take_im1 = range_sum(i-1, k+1, j);
                best_k = max(best_k, take_i + take_im1);
            }
            dp[i][j][2] = max(dp[i][j][2], best0 + best_k);
        }

        // --- dp[i][j][1]: take in col i from bottom..j, caught by left neighbor col (i-1) ---
        // Require left pier height k >= j. We extend from dp[i-1][k][0].
        for (int j = 0; j <= N; ++j) {
            for (int k = j; k <= N; ++k) {
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][k][0] + cost[i][j]);
            }
        }

        // --- dp[i][j][0]: block up to j in col i ---
        // Either:
        // 1) we previously blocked col (i-1) up to k, and now catch (i-1)'s fish in (k, j] via right pier j, or
        // 2) carry over a configuration where col (i-1) already took (states 1 or 2) up to the same j.
        for (int j = 0; j <= N; ++j) {
            // case (1): catch from left column thanks to current right pier j
            for (int k = 0; k <= j; ++k) {
                dp[i][j][0] = max(dp[i][j][0],
                                  dp[i-1][k][0] + range_sum(i-1, k+1, j));
            }
            // case (2): carry over
            dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][1]);
            dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][2]);
        }

        // Monotonicity: blocking more (bigger j) cannot hurt
        for (int j = N-1; j >= 0; --j) {
            dp[i][j][0] = max(dp[i][j][0], dp[i][j+1][0]);
        }
    }

    // Answer is the best at column N over all heights and states
    ll ans = 0;
    if (N == 1) return 0; // cannot catch anything with only one column
    for (int j = 0; j <= N; ++j) {
        ans = max(ans, dp[N][j][0]);
        ans = max(ans, dp[N][j][1]);
        ans = max(ans, dp[N][j][2]);
    }
    return ans;
}

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