제출 #1179486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179486		gyg	메기 농장 (IOI22_fish)	C++20	35 / 100	112 ms	5704 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector
const int N = 3e2 + 5;

int n;
arr<arr<int, N>, N> a;

arr<arr<int, N>, N> sm;
int rng(int i, int l, int r) {
    if (l > r) return 0;
    return sm[i][r] - sm[i][l - 1];
}
void sm_cmp() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sm[i][j] = sm[i][j - 1] + a[i][j];
        }
    }
}

arr<arr<arr<int, 2>, N>, N> dp;
void slv(int i, int x, int b) {
    dp[i][x][b] = rng(i - 1, 1, x);

    if (b == 1) {
        if (i - 1 >= 1) {
            for (int y = x; y <= n; y++) {
                for (int c : {0, 1}) {
                    dp[i][x][b] = max(dp[i][x][b], dp[i - 1][y][c] + rng(i, x + 1, y));
                }
            }
        }
        // cout << i << " " << x << " " << b << ": " << dp[i][x][b] << '\n';
        return;
    }

    if (i - 3 >= 1) {
        for (int y = 1; y <= n; y++) {
            for (int c : {0, 1}) {
                dp[i][x][b] = max(dp[i][x][b], dp[i - 3][y][c] + rng(i - 2, 1, y) + rng(i - 1, 1, x));
            }
        }
    }
    if (i - 2 >= 1) {
        for (int y = x; y <= n; y++) {
            for (int c : {0, 1}) {
                dp[i][x][b] = max(dp[i][x][b], dp[i - 2][y][c] + rng(i - 1, 1, y));
            }
        }
        for (int y = 1; y <= x - 1; y++) {
            for (int c : {0, 1}) {
                dp[i][x][b] = max(dp[i][x][b], dp[i - 2][y][c] + rng(i - 1, 1, x));
            }
        }
    }
    if (i - 1 >= 1) {
        for (int y = 1; y <= x - 1; y++) {
            dp[i][x][b] = max(dp[i][x][b], dp[i - 1][y][0] + rng(i - 1, y + 1, x));
        }
    } 

    // cout << i << " " << x << " " << b << ": " << dp[i][x][b] << '\n';
}
void dp_cmp() {
    for (int i = 1; i <= n; i++)
        for (int x = 1; x <= n; x++)
            for (int b : {0, 1})
                slv(i, x, b);
}

int max_weights(sig _n, sig _m, vec<sig> _x, vec<sig> _y, vec<sig> _w) {
    n = _n;
    for (int i = 0; i < _m; i++) a[_x[i] + 1][_y[i] + 1] = _w[i];

    sm_cmp();
    dp_cmp();

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int x = 1; x <= n; x++) {
            for (int b : {0, 1}) {
                ans = max(ans, dp[i][x][b] + rng(i + 1, 1, x));
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16