Submission #845820

#	Time	Username	Problem	Language	Result	Execution time	Memory
845820		Sorting	축구 경기장 (IOI23_soccer)	C++17	64 / 100	2165 ms	752944 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 3;

bool f[N][N];
int prefix[N][N];
short p2[N][N][N], prv[N][N][N], nxt[N][N][N];
int n;

int dp[2][N][N];

int get_sum(int i, int l, int r){
    if(l == 0)
        return prefix[i][r];
    return prefix[i][r] - prefix[i][l - 1];
}

bool bad(int l1, int r1, int l2, int r2){
    if(l1 <= l2 && r2 <= r1)
        return false;
    if(l2 <= l1 && r1 <= r2)
        return false;
    return true;
}

pair<int, int> extend(int i, int j, int l, int r){
    assert(prv[l][r][i] == prv[l][r][j]);
    assert(nxt[l][r][i] == nxt[l][r][j]);
    return {prv[l][r][i], nxt[l][r][j]};
}

int global_ans = 0;

void init_dp(){
    for(int l = n - 1; l >= 0; --l){
        for(int r = l; r < n; ++r){
            for(int i = 0; i < n; ++i){
                if(p2[l][r][i])
                    continue;
                auto [p, q] = extend(i, i, l, r);

                auto &ans = dp[l & 1][r][p];
                ans = 0;

                if(l != r){
                    vector<pair<int, int>> v{{l + 1, r}, {l, r - 1}};
                    for(auto [l2, r2]: v){
                        auto [p2, q2] = extend(p, q, l2, r2);

                        int cand = (p - p2 + q2 - q) * (r2 - l2 + 1);
                        cand += dp[l2 & 1][r2][p2];
                        ans = max(ans, cand);
                    }
                }

                global_ans = max(global_ans, ans + (q - p + 1) * (r - l + 1));
            }
        }
    }
}

int biggest_stadium(int _N, std::vector<std::vector<int>> F){
    n = _N;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            f[i][j] = F[i][j];

    for(int i = 0; i < n; ++i){
        prefix[i][0] = f[i][0];
        for(int j = 1; j < n; ++j)
            prefix[i][j] = prefix[i][j - 1] + f[i][j];
    }

    for(int l = 0; l < n; ++l){
        for(int r = l; r < n; ++r){
            for(int i = 0; i < n; ++i){
                p2[l][r][i] = (bool)get_sum(i, l, r);
            }
        }
    }

    for(int l = 0; l < n; ++l){
        for(int r = l; r < n; ++r){
            int x = 0;
            for(int i = 0; i < n; ++i){
                if(p2[l][r][i]){
                    x = i + 1;
                }
                else{
                    prv[l][r][i] = x;
                }
            }

            x = n - 1;
            for(int i = n - 1; i >= 0; --i){
                if(p2[l][r][i]){
                    x = i - 1;
                }
                else{
                    nxt[l][r][i] = x;
                }
            }
        }
    }

    init_dp();

    return global_ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/

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