Submission #842641

#	Time	Username	Problem	Language	Result	Execution time	Memory
842641		nonono	Soccer Stadium (IOI23_soccer)	C++17	54 / 100	239 ms	47404 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

void upMax(int &x, int y) {
    x = max(x, y);
}

int sub1(int N, vector<vector<int>> F) {
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(F[i][j] == 1) {
                return max({
                    N * i + N * j - i * j,
                    N * i + N * (N - j - 1) - i * (N - j - 1),
                    N * (N - i - 1) + N * j - (N - i - 1) * j,
                    N * (N - i - 1) + N * (N - j - 1) - (N - i - 1) * (N - j - 1) 
                });
            }
        }
    }
    
    return N * N;
}

int sub4(int N, vector<vector<int>> F) {
    for(int i = 0; i < N; i ++) {
        partial_sum(F[i].begin(), F[i].end(), F[i].begin());
    }
    
    auto get_sum = [&] (int row, int l, int r) {
        return F[row][r] - (!l ? 0 : F[row][l - 1]);
    };
    
    vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>> (N, vector<vector<int>> (N, vector<int> (N, -1))));
    int result = 0;
    
    for(int first_row = N - 1; first_row >= 0; first_row --) {
        for(int last_row = first_row; last_row < N; last_row ++) {
            
            for(int l = 0; l < N; l ++) {
                for(int r = l; r < N; r ++) {
                    if(!get_sum(first_row, l, r)) {
                        dp[first_row][first_row][l][r] = r - l + 1;
                        upMax(result, dp[first_row][first_row][l][r]);
                    }
                }
            }
            
            for(int l = 0; l < N; l ++) {
                for(int r = l; r < N; r ++) {
                    
                    for(int _l = l; _l <= r; _l ++) {
                        for(int _r = _l; _r <= r; _r ++) {
                            
                            if(first_row + 1 < N && dp[first_row + 1][last_row][l][r] != -1 && !get_sum(first_row, _l, _r)) {
                                upMax(dp[first_row][last_row][_l][_r], dp[first_row + 1][last_row][l][r] + _r - _l + 1);
                            } 
                            
                            if(last_row - 1 >= 0 && dp[first_row][last_row - 1][l][r] != -1 && !get_sum(last_row, _l, _r)) {
                                upMax(dp[first_row][last_row][_l][_r], dp[first_row][last_row - 1][l][r] + _r - _l + 1);
                            }
                            
                            upMax(result, dp[first_row][last_row][_l][_r]);
                        }
                    }
                }
            }
        }
    }
    
    return result;
}

int biggest_stadium(int N, vector<vector<int>> F) {
    if(N <= 30) return sub4(N, F);
    return sub1(N, F);
}

/*int main() {
    int N;
    cin >> N;
    
    vector<vector<int>> F(N, vector<int> (N));
    
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> F[i][j];
        }
    }
    
    cout << biggest_stadium(N, F) << "\n";
    return 0;
}*/

• 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