Submission #1263884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263884		nicolo_010	Catfish Farm (IOI22_fish)	C++20	0 / 100	967 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][10][10][10];

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<10; i++) {
        for (int j=0; j<10; j++) {
            for (int k=0; k<10; k++) {
                dp[0][i][j][k] = 0;
            }
        }
    }
    vector<vector<ll>> mx(10, vector<ll>(10, 0));
    for (int i=1; i<=N; i++) {
        cout << i << endl;
        for (int j=0; j<10; j++) {
            for (int k1=0; k1<10; k1++) {
                for (int k2=0; k2<10; k2++) {
                    dp[i][j][k1][k2] = mx[k1][k2];
                    //if (j == 0 && k1 == 5 && k2 == 0) cout << mx[k1][k2] << endl;
                }
            }
        }
        cout << i << endl;
        vector<vector<ll>> newmx(10, vector<ll>(10, 0));
        for (int j=0; j<10; j++) {
            for (int k1=0; k1<10; k1++) {
                for (int k2=0; k2<10; k2++) {
                    if (max(j, k2) > N || k1 > N) continue;
                    int mn = (i == 1 ? j : min(j, k2));
                    if (i == N) mn = k2;
                    ll sum = (mn > 0 ? prefix[i-1][mn-1] : 0);
                    sum -= (k1 > 0 ? prefix[i-1][k1-1] : 0);
                    sum = max(0ll, sum);
                    dp[i][j][k1][k2] = max(dp[i][j][k1][k2], sum+mx[k1][k2]);
                    //if (j == 5 && k1 == 0) cout << mx[j][k1] << endl;
                    cout << j << " " << k1 << " " << k2 << " " << dp[i][j][k1][k2] << endl;
                    newmx[j][k1] = max(newmx[j][k1], dp[i][j][k1][k2]);
                }
            } 
        }
        mx = newmx;
    }
    ll ans = 0;
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            for (int k=0; k<10; k++) {
                if (max(i, k) > N || j > N) continue;
                ans = max(ans, dp[N][i][j][k]);
            }
        }
    }
    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