Submission #1210786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210786		qwusha	Catfish Farm (IOI22_fish)	C++20	0 / 100	956 ms	2162688 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    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 = 1; j < n; j++) {
            a[i][j] += a[i][j - 1];
        }
    }
    int K = 8;
    if (n < K) {
        K = n;
    }
    vector<vector<vector<vector<ll>>>> dp(n - 2, vector<vector<vector<ll>>>(K + 1, vector<vector<ll>>(K + 1, vector<ll>(K + 1))));
    if (n == 2) {
        return max(a[0][n - 1], a[1][n - 1]);
    }
    ll res = 0;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= K; j++) {
            for (int q = 0; q <= K; q++) {
                int val = 0;
                if (n > 3) {
                    val = a[3][q];
                }
                int v2 = max(0, a[2][j] - a[2][q]);
                int v1 = max(0, max(a[1][i], a[1][q]) - a[1][j]);
                int v0 = max(0, a[0][j] - a[0][i]);
                dp[0][i][j][q] = val + v0 + v1 + v2;
                res = max(res, dp[0][i][j][q]);
            }
        }
    }
    for (int beg = 1; beg < n - 2; beg++) {
        for (int i = 0; i <= K; i++) {
            for (int j = 0; j <= K; j++) {
                for (int q = 0; q <= K; q++) {
                    for (int k = 0; k <= K; k++) {
                        int val = 0;
                        if (beg < n - 3) {
                            val = a[beg + 3][q];
                        }
                        ll nv = dp[beg - 1][k][i][j];
                        nv += val;
                        nv -= a[beg + 2][min(j, q)];
                        nv += max(0, a[beg + 1][q] - a[beg + 1][max(i, j)]);
                        dp[beg][i][j][q] = max(dp[beg][i][j][q], nv);
                    }
                    res = max(res, dp[beg][i][j][q]);
                }
            }
        }
    }
    return res;
}

/*
signed main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m), y(m), w(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i] >> w[i];
    }
    cout << max_weights(n,m,x,y,w) << '\n';
}*/

• 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