제출 #1226536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226536		ericl23302	메기 농장 (IOI22_fish)	C++20	23 / 100	258 ms	135752 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vector<vector<ll>> vals(N, vector<ll>(10, 0));
    for (int i = 0; i < M; ++i) vals[X[i]][Y[i] + 1] += W[i];
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j < 10; ++j) vals[i][j] += vals[i][j - 1];
    }

    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(10, vector<ll>(10, 0)));
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (!i && !j) continue;
            dp[0][i][j] = LLONG_MIN / 2;
        }
    }

    for (int i = 0; i < N; ++i) {
        vector<vector<ll>> &prevDp = dp[i], &curDp = dp[i + 1];
        for (int prev2 = 0; prev2 < 10; ++prev2) {
            for (int prev = 0; prev < 10; ++prev) {
                for (int cur = 0; cur < 10; ++cur) {
                    ll additional = max(0ll, vals[i][prev] - vals[i][cur]);
                    if (i && cur > max(prev2, prev)) additional += vals[i - 1][cur] - vals[i - 1][max(prev2, prev)];
                    curDp[prev][cur] = max(curDp[prev][cur], prevDp[prev2][prev] + additional);
                }
            }
        }
    }

    ll res = 0;
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) res = max(res, dp[N][i][j]);;
    }

    return res;
}

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