Submission #1205822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205822		Pacybwoah	Soccer Stadium (IOI23_soccer)	C++20	54 / 100	695 ms	63184 KiB

soccer

#include "soccer.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
    const int inf = 1e9;
    int dp[31][31][31][31];
}
int biggest_stadium(int N, std::vector<std::vector<int>> F){
    int n = N, ans = 0, cnt = 0;
    vector<vector<int>> vec(n + 1, vector<int>(n + 1)), pre(n + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            vec[i][j] = 1 - F[i - 1][j - 1];
            cnt += vec[i][j];
        }
    }
    if(cnt == n * n) return n * n;
    if(cnt == n * n - 1){
        int px = -1, py = -1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(vec[i][j] == 0) px = i, py = j;
            }
        }
        return n * n - min(px, n - px + 1) * min(py, n - py + 1);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + vec[i][j];
        }
    }
    auto get = [&](int a, int b, int c, int d){
        // (a, b) -> (c, d)
        return pre[c][d] - pre[c][b - 1] - pre[a - 1][d] + pre[a - 1][b - 1];
    };
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                for(int l = 1; l <= n; l++){
                    dp[i][j][k][l] = -inf;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = j; k <= n; k++){
                if(get(i, j, i, k) == k - j + 1) dp[i][i][j][k] = k - j + 1;
            }
        }
    }
    for(int len = 1; len < n; len++){
        for(int t = 1; t + len - 1 <= n; t++){
            int b = t + len - 1;
            for(int l = 1; l <= n; l++){
                for(int r = l; r <= n; r++){
                    if(dp[t][b][l][r] == -inf) continue;
                    for(int tl = l; tl <= r; tl++){
                        for(int tr = tl; tr <= r; tr++){
                            if(t > 1 && get(t - 1, tl, t - 1, tr) == tr - tl + 1) dp[t - 1][b][tl][tr] = max(dp[t - 1][b][tl][tr], dp[t][b][l][r] + tr - tl + 1);
                            if(b < n && get(b + 1, tl, b + 1, tr) == tr - tl + 1) dp[t][b + 1][tl][tr] = max(dp[t][b + 1][tl][tr], dp[t][b][l][r] + tr - tl + 1);
                        }
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                for(int l = 1; l <= n; l++){
                    ans = max(ans, dp[i][j][k][l]);
                }
            }
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30