Submission #841587

#	Time	Username	Problem	Language	Result	Execution time	Memory
841587		I_love_Hoang_Yen	Soccer Stadium (IOI23_soccer)	C++17	61 / 100	284 ms	31836 KiB

soccer

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

struct Row {
    int first, last;
    int cnt() const {
        return last - first + 1;
    }
    bool contains(const Row& b) const {
        return first <= b.first && b.last <= last;
    }
    bool operator < (const Row& b) const {
        return cnt() > b.cnt();
    }
};

pair<bool, int> subtask_25p(int n, const vector<vector<int>>& forest) {
    int cnt_row = 0; // number of non-empty rows
    int first_row = n, last_row = -1;
    int total = 0;
    vector<Row> rows;

    for (int r = 0; r < n; ++r) {
        int cnt = 0; // number of empty cells
        int first = n, last = -1; // all empty cells should be in [first, last]
        for (int c = 0; c < n; ++c) {
            if (forest[r][c] == 0) {
                ++total;
                ++cnt;
                if (first == n) first = c;
                last = c;
            }
        }
        // ignore empty rows
        if (cnt == 0) continue;

        if (first_row == n) first_row = r;
        last_row = r;
        ++cnt_row;

        // Condition: in each row, there should be only 1 sequence of 0
        if (cnt != last - first + 1) return {false, -1};

        rows.push_back(Row{first, last});
    }

    // Condition: all rows with empty cells must be consecutive
    if (cnt_row != last_row - first_row + 1) return {false, -2};

    // From biggest row, each row should contains the row next to (& further away from) it
    int largest_row = min_element(rows.begin(), rows.end()) - rows.begin();
    for (int i = largest_row; i > 0; --i) {
        if (!rows[i].contains(rows[i-1])) return {false, -3};
    }
    for (int i = largest_row; i + 1 < (int) rows.size(); ++i) {
        if (!rows[i].contains(rows[i+1])) return {false, -4};
    }

    // In decreasing order of size, row should contains next row
    sort(rows.begin(), rows.end());
    for (int i = 0; i + 1 < (int) rows.size(); ++i) {
        if (!rows[i].contains(rows[i+1])) return {false, -5};
    }

    return {true, total};
}

int dp[33][33][33][33];
void upMax(int& f, int val) {
    if (val > f) f = val;
}

int sub4(int n, vector<vector<int>> forest) {
    for (int i = 0; i < n; ++i) {
        std::partial_sum(forest[i].begin(), forest[i].end(), forest[i].begin());
    }
    auto get_sum = [&] (int row, int l, int r) { // [l, r]
        return forest[row][r] - (l == 0 ? 0 : forest[row][l-1]);
    };

    memset(dp, -1, sizeof dp);
    for (int first_row = n-1; first_row >= 0; --first_row) {
        for (int last_row = first_row; last_row < n; ++last_row) {
            // base case: only 1 row
            if (first_row == last_row) {
                for (int l = 0; l < n; ++l) {
                    for (int r = l; r < n; ++r) {
                        if (get_sum(first_row, l, r) == 0) {
                            dp[first_row][first_row][l][r] = r - l + 1;
                        }
                    }
                }
            }
            
            // update: add 1 row above
            if (first_row > 0) {
                for (int l = 0; l < n; ++l) {
                    for (int r = l; r < n; ++r) {
                        int cur = dp[first_row][last_row][l][r];
                        if (cur < 0) continue;

                        for (int l2 = l; l2 <= r; l2++) {
                            for (int r2 = l2; r2 <= r; r2++) {
                                if (get_sum(first_row - 1, l2, r2) == 0) {
                                    upMax(dp[first_row - 1][last_row][l2][r2], cur + r2 - l2 + 1);
                                }
                            }
                        }
                    }
                }
            }
            // update: add 1 row below
            if (last_row + 1 < n) {
                for (int l = 0; l < n; ++l) {
                    for (int r = l; r < n; ++r) {
                        int cur = dp[first_row][last_row][l][r];
                        if (cur < 0) continue;

                        for (int l2 = l; l2 <= r; l2++) {
                            for (int r2 = l2; r2 <= r; r2++) {
                                if (get_sum(last_row + 1, l2, r2) == 0) {
                                    upMax(dp[first_row][last_row + 1][l2][r2], cur + r2 - l2 + 1);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    int res = 0;
    for (int r1 = 0; r1 < n; ++r1) {
        for (int r2 = r1; r2 < n; ++r2) {
            for (int c1 = 0; c1 < n; ++c1) {
                for (int c2 = c1; c2 < n; ++c2) {
                    upMax(res, dp[r1][r2][c1][c2]);
                }
            }
        }
    }
    return res;
}

int biggest_stadium(int n, vector<vector<int>> forest) {
    auto [is_good, cnt] = subtask_25p(n, forest);
    if (is_good) return cnt;
    if (n <= 30) return sub4(n, forest);
    return 0;
}

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