제출 #979977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979977		vjudge1	Soccer Stadium (IOI23_soccer)	C++17	16 / 100	4552 ms	47396 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using vvi = vector <vi>;
using vll = vector <ll>;

int biggest_stadium (int n, vvi f) {
    ll all = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            all += f[i][j] == 0;
        }
    }
    vvi ps(n+1, vi(n+1, 0));
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++)
            ps[i+1][j+1] = !f[i][j];
    for (ll i = 0; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            ps[i][j] += ps[i][j-1];
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= n; j++) {
            ps[i][j] += ps[i-1][j];
        }
    }
    auto query = [&](ll il, ll ir, ll jl, ll jr) { // [il, ir] and [jl, jr] 0-indexed
        ir++; jr++;
        return ps[ir][jr] - ps[ir][jl] - ps[il][jr] + ps[il][jl];
    };
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (f[i][j]) continue;
            ll il = i, ir = i;
            ll jl = j, jr = j;
            while (il >= 0 && !f[il][j]) il--;
            while (ir <= n-1 && !f[ir][j]) ir++;
            while (jl >= 0 && !f[i][jl]) jl--;
            while (jr <= n-1 && !f[i][jr]) jr++;
            ll cou = 0;
            cou += query(0, il, 0, jl);
            cou += query(ir, n-1, 0, jl);
            cou += query(0, il, jr, n-1);
            cou += query(ir, n-1, jr, n-1);
            if (cou != 0) return 0;
        }
    }
    for (ll i = 0; i < n; i++) {
        ll j = 0;
        for (; j < n; j++) if (!f[i][j]) break;
        for (; j < n; j++) if (f[i][j]) break;
        for (; j < n; j++) if (!f[i][j]) break;
        if (j != n) return 0;
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < i; j++) {
            swap(f[i][j], f[j][i]);
        }
    }
    for (ll i = 0; i < n; i++) {
        ll j = 0;
        for (; j < n; j++) if (!f[i][j]) break;
        for (; j < n; j++) if (f[i][j]) break;
        for (; j < n; j++) if (!f[i][j]) break;
        if (j != n) return 0;
    }
    return all;
}

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