제출 #1126838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126838		Pannda	메기 농장 (IOI22_fish)	C++20	37 / 100	1122 ms	1602932 KiB

fish

#include "fish.h"

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

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template<typename... Args>
    Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
    }
};
template<typename T>
struct Vec<1, T> : public vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
    }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    int n = N, m = M;
    Vec<2, array<int, 2>> a(n);
    for (int i = 0; i < m; i++) {
        a[X[i]].push_back({Y[i], W[i]});
    }

    for (int i = 0; i < n; i++) {
        a[i].push_back({n, 0});
        sort(a[i].begin(), a[i].end());
    }

    Vec<2, long long> prev(a[0].size(), a[1].size(), 0);
    for (int x = 0; x < a[0].size(); x++) {
        for (int y = 0; y < a[1].size(); y++) {
            for (int i = x; i < a[0].size(); i++) {
                if (a[0][i][0] < a[1][y][0]) prev[x][y] += a[0][i][1];
            }
            for (int i = y; i < a[1].size(); i++) {
                if (a[1][i][0] < a[0][x][0]) prev[x][y] += a[1][i][1];
            }
        }
    }

    for (int col = 2; col < n; col++) {
        Vec<2, long long> dp(a[col - 1].size(), a[col].size(), 0);
        for (int x = 0; x < a[col - 2].size(); x++) {
            for (int y = 0; y < a[col - 1].size(); y++) {
                for (int z = 0; z < a[col].size(); z++) {
                    long long val = 0;
                    for (int i = y; i < a[col - 1].size(); i++) {
                        if (a[col - 1][i][0] >= a[col - 2][x][0] && a[col - 1][i][0] < a[col][z][0]) val += a[col - 1][i][1];
                    }
                    for (int i = z; i < a[col].size(); i++) {
                        if (a[col][i][0] < a[col - 1][y][0]) val += a[col][i][1];
                    }
                    dp[y][z] = max(dp[y][z], prev[x][y] + val);
                }
            }
        }
        prev = dp;
    }

    long long ans = 0;
    for (vector<long long> v : prev) {
        ans = max(ans, *max_element(v.begin(), v.end()));
    }

    return ans;
}

• 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: 14 / 14
• Subtask 8: 0 / 16