Submission #1241809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241809		repsak	Catfish Farm (IOI22_fish)	C++20	0 / 100	796 ms	1669628 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    int offset = 3;
    int rightOff = 3;
    vector<vector<ll>> grid(N + offset + rightOff, vector<ll>(N)), prefix(N + offset + rightOff, vector<ll>(N));
    vector<vector<vector<ll>>> dp(N + offset + rightOff, vector<vector<ll>>(N, vector<ll>(3)));

    // dp[x][y][0] = includex mid, right
    //         [1] = excluded right
    //         [2] = excluded mid & right

    for(int i = 0; i < M; i++){
        grid[offset + X[i]][Y[i]] = W[i];
    }

    // Create prefix sums: 
    for(int x = offset; x < N + offset; x++){
        prefix[x][0] = grid[x][0];

        for(int y = 1; y < N; y++){
            prefix[x][y] = prefix[x][y - 1] + grid[x][y];
        }
    }

    // calc dp
    for(int xF = 0; xF < N; xF++){
        int x = xF + offset;

        for(int y = 0; y < N; y++){

            for(int h = 0; h < N; h++){

                // dp[i] = dp[i - 3]
                dp[x][y][0] = max(
                    dp[x][y][0],
                    dp[x - 3][h][0] + prefix[x - 1][y] + prefix[x + 1][y]
                );
                
                dp[x][y][1] = max(
                    dp[x][y][1],
                    dp[x - 3][h][0] + prefix[x - 1][y]
                );

                dp[x][y][2] = max(
                    dp[x][y][2],
                    dp[x - 3][h][0] + prefix[x - 1][y]
                );

                // dp[i] = dp[i - 2]
                if(x >= offset + 2){
                    dp[x][y][0] = max(
                        dp[x][y][0],
                        dp[x - 2][h][1] + prefix[x + 1][y] + prefix[x - 1][max(y, h)]
                    );
    
                    
                    dp[x][y][1] = max(
                        dp[x][y][1],
                        dp[x - 2][h][1] + prefix[x - 1][max(y, h)]
                    );
                    
                    dp[x][y][2] = max(
                        dp[x][y][2],
                        dp[x - 2][h][1] + prefix[x - 1][max(y, h)]
                    );
                }


                // dp[i] = dp[i - 1]
                ll additional = 0;
                ll excludedMid = 1;

                if(x >= offset + 1){
                    if(y > h){
                        additional = prefix[x - 1][y] - prefix[x - 1][h];
                    }else if(h > y){
                        additional = prefix[x][h] - prefix[x][y];
                        excludedMid = 0;
                    }

                    assert(additional >= 0);

                    dp[x][y][0] = max({
                        dp[x][y][0],
                        dp[x - 1][h][0],
                        // dp[x - 1][y][0],
                        // dp[x - 1][h][1] + prefix[x + 1][y],
                        dp[x - 1][h][2] + additional + prefix[x + 1][y]
                    });
    
                    dp[x][y][1] = max({
                        dp[x][y][1],
                        dp[x - 1][h][0],  // <-- might want to add again (only here)
                        dp[x - 1][h][2] + additional
                    });
    
                    dp[x][y][2] = max({
                        dp[x][y][2],
                        dp[x - 1][h][1],
                        dp[x - 1][h][2] + additional * excludedMid
                    });
                }


                // cout << "new\n";
            }
        }
    }

    ll best = 0;
    for(int x = 0; x < N; x++){
        for(int y = 0; y < N; y++){
            best = max({
                best, 
                dp[offset + x][y][0],
                dp[offset + x][y][1],
                dp[offset + x][y][2],
            });
        }
    }

    return best;
}

// #include "grader.cpp"

• 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