Submission #1079612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079612		alontanay	Soccer Stadium (IOI23_soccer)	C++17	77.50 / 100	293 ms	39764 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2005;

int U[MAX_N][MAX_N];
int D[MAX_N][MAX_N];

int segUmin[MAX_N][MAX_N];
int segDmin[MAX_N][MAX_N];

int dp[MAX_N][MAX_N];

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    int cnt = 0;
    for(vector<int> &row : F) {
        for(int cell : row) {
            cnt += cell;
        }
    }
    if(cnt == 0) { return N*N; }
    else if(cnt == 1) {
        for(int r = 0; r < N; r ++) {
            for(int c = 0; c < N; c ++) {
                if(F[r][c]) {
                    r = min(r+1,N-r);
                    c = min(c+1,N-c);
                    return N*N-r*c;
                }
            }
        }
    }
    if(N > 500) {
        for(int r = 0; r < N; r ++) {
            int lst = 1;
            int switches = 0;
            for(int c = 0; c < N; c ++) {
                switches += lst^F[r][c];
                lst = F[r][c];
            }
            switches += lst^1;
            if(switches > 2) {
                return MAX_N*MAX_N;
            }
        }
        for(int c = 0; c < N; c ++) {
            int lst = 1;
            int switches = 0;
            for(int r = 0; r < N; r ++) {
                switches += lst^F[r][c];
                lst = F[r][c];
            }
            switches += lst^1;
            if(switches > 2) {
                return MAX_N*MAX_N;
            }
        }
        vector<pair<int,int>> segs;
        for(int r = 0; r < N; r ++) {
            int st = N, en = 0;
            for(int c = 0; c < N; c ++) {
                if(!F[r][c]) {
                    st = min(st,c);
                    en = max(en,c);
                }
            }
            if(st <= en) {
                segs.push_back({st,-en});
            }
        }
        sort(segs.begin(),segs.end());
        for(int i = 0; i < (int)(segs.size())-1; i ++) {
            if(segs[i].second > segs[i+1].second) { return MAX_N*MAX_N; }
        }
        return N*N-cnt;
    }
    for(int c = 0; c < N; c ++) {
        int lst = -1;
        for(int r = 0; r < N; r ++) {
            if(F[r][c]) { lst = r; }
            U[r][c] = r-lst;
        }
        lst = N;
        for(int r = N-1; r >= 0; r--) {
            D[r][c] = lst-r-1;
            if(F[r][c]) { lst = r; }
        }
    }
    int res = 0;
    for(int r = 0; r < N; r ++) {
        for(int i = 0; i < N; i ++) {
            segUmin[i][i] = MAX_N;;
            for(int j = i + 1; j <= N; j ++) {
                segUmin[i][j] = min(segUmin[i][j-1],U[r][j-1]);
            }
            segDmin[i][i] = MAX_N;
            for(int j = i + 1; j <= N; j ++) {
                segDmin[i][j] = min(segDmin[i][j-1],D[r][j-1]);
            }
        }
        for(int sz = 1; sz <= N; sz ++) {
            for(int r = sz; r <= N; r ++) {
                int l = r-sz;
                int cur_h = segUmin[l][r] + segDmin[l][r];
                dp[l][r] = max(dp[l][r-1],dp[l+1][r]) + cur_h;
            }
        }
        res = max(res,dp[0][N]);
    }
    return res;
}

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