제출 #875087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875087		TheQuantiX	축구 경기장 (IOI23_soccer)	C++17	6 / 100	241 ms	39700 KiB

soccer

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

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
vector< vector<int> > f;
vector< vector<ll> > pref;

inline ll on_rectangle(ll u, ll l, ll d, ll r) {
    return pref[d + 1][r + 1] - pref[d + 1][l] - pref[u][r + 1] + pref[u][l];
}

inline int check(ll u, ll l, ll d, ll r) {
    // cout << u << ' ' << l << ' ' << d << ' ' << r << endl;
    int ans = 0;
    for (int lp = u; lp <= d; lp++) {
        for (int up = l; up <= r; up++) {
            if (on_rectangle(lp, l, lp, r) != 0) {
                continue;
            }
            if (on_rectangle(u, up, d, up) != 0) {
                continue;
            }
            // cout << '\t' << lp << ' ' << rp << ' ' << up << ' ' << dp << endl;
            // cout << '\t' << on_rectangle(u, l, lp - 1, up - 1) << ' ' << on_rectangle(u, up + 1, rp - 1, r) << ' ' << on_rectangle(lp + 1, l, d, dp - 1) << ' ' << on_rectangle(rp + 1, dp + 1, d, r) << ' ' << on_rectangle(u, l, d, r) << '\n';
            int cnt = (d - u + 1) * (r - l + 1);
            vector< vector<ll> > DP(d - u + 1, vector<ll>(r - l + 1, 1));
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp - 1; i >= u; i--) {
                for (int j = up - 1; j >= l; j--) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i + 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j + 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp - 1; i >= u; i--) {
                for (int j = up + 1; j <= r; j++) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i + 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j - 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp + 1; i <= d; i++) {
                for (int j = up - 1; j >= l; j--) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j + 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp + 1; i <= d; i++) {
                for (int j = up + 1; j <= r; j++) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j - 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            // cout << "\t" << cnt << endl;
            ans = max(ans, cnt);
        }
    }
    // cout << ans << endl;
    return ans;
}

int solve1(vector< vector<int> > F) {
    f = F;
    pref.resize(n + 1);
    for (int i = 0; i < n + 1; i++) {
        pref[i].resize(n + 1);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + F[i][j];
        }
    }
    int ans = 0;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = i1; i2 < n; i2++) {
            for (int j1 = 0; j1 < n; j1++) {
                for (int j2 = j1; j2 < n; j2++) {
                    ans = max(ans, check(i1, j1, i2, j2));
                }
            }
        }
    }
    return ans;
}

int biggest_stadium(int N, vector< vector<int> > F) {
    n = N;
    if (n <= 7) {
        return solve1(F);
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (F[i][j] == 1) {
                return n * n - min(min((i + 1) * (j + 1), (n - i) * (j + 1)), min((i + 1) * (n - j), (n - i) * (n - j)));
            }
        }
    }
    return n * n;
}

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