Submission #1263890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263890		nicolo_010	Catfish Farm (IOI22_fish)	C++20	0 / 100	1018 ms	2162688 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define cout if(0) cout 
const int mxN = 300;

ll dp[mxN+1][mxN+1];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vector<vector<ll>> prefix(N, vector<ll>(N, 0));
    // prefix[i][j] = suma de todos los catfish de la columna i hasta fila j
    for (int i=0; i<M; i++) {
        prefix[X[i]][Y[i]]+=W[i];
    }
    for (int i=0; i<N; i++) {
        for (int j=1; j<N; j++) {
            prefix[i][j] += prefix[i][j-1];
        }
    }
    for (int i=0; i<=N; i++)  {
        dp[0][i] = 0;
    }
    vector<vector<ll>> mx(10, vector<ll>(10, 0));
    for (int i=1; i<N; i++) {
        for (int j=0; j<=N; j++) {
            ll sum = 0;
            if (i == N-1 && j>0) {
                sum = prefix[i][j-1];
            }
            dp[i][0] = max(dp[i][0], dp[i-1][j] + sum);
        }
        for (int j=1; j<=N; j++) {
            ll mx=0;
            if (i == 1) {
                mx = prefix[0][j-1];
            }
            else {
                for (int k=0; k <= N; k++) {
                    int mn = min(j, k);
                    ll sum = (mn > 0 ? prefix[i-1][mn-1] : 0);
                    mx = max(mx, dp[i-2][k]+sum);
                }
            }
            ll case2 = 0;
            for (int k=0; k<=N; k++) {
                case2 = max(case2, dp[i-1][k]);
            }
            dp[i][j] = max({
                dp[i][j], mx, case2
            });
        }
    }
    ll ans = 0;
    for (int i=0; i<=N; i++) {
        ans = max(dp[N-1][i], ans);
    }
    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