제출 #1261319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261319		biank	Soccer Stadium (IOI23_soccer)	C++20	14 / 100	205 ms	47676 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;

const int MAX_N = 2005;

int pref[MAX_N][MAX_N], n;
vector<ii> ran[MAX_N];

int query(int i1, int i2, int j1, int j2) {
    i2++, j2++;
    return pref[i2][j2] - pref[i1][j2] - pref[i2][j1] + pref[i1][j1];
}

bool isMaximal(int i1, int i2, int j1, int j2) {
    if (query(i1, i2, j1, j2) > 0) return false;
    if (i1 > 0 && query(i1 - 1, i2, j1, j2) == 0) return false;
    if (i2 + 1 < n && query(i1, i2 + 1, j1, j2) == 0) return false;
    if (j1 > 0 && query(i1, i2, j1 - 1, j2) == 0) return false;
    if (j2 + 1 < n && query(i1, i2, j1, j2 + 1) == 0) return false;
    return true;
}

ii getMaximal(int i, int l, int r) {
    assert(query(i, i, l, r) == 0);
    int lo = i, hi = n;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (query(i, mid, l, r) == 0) lo = mid;
        else hi = mid;
    }
    int i2 = lo;
    lo = -1, hi = i;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (query(mid, i, l, r) == 0) hi = mid;
        else lo = mid;
    }
    int i1 = hi;
    assert(isMaximal(i1, i2, l, r));
    return ii{i1, i2};
}

vector<ii> getRanges(int i, int l, int r) {
    int lo = -1, hi = sz(ran[i]);
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (ran[i][mid].snd >= l) hi = mid;
        else lo = mid;
    }
    int j = hi;
    if (j == sz(ran[i])) return {};
    vector<ii> ret;
    ret.eb(max(ran[i][j].fst, l), min(ran[i][j].snd, r));
    j++;
    while (j < sz(ran[i]) && ran[i][j].fst <= r) {
        ret.eb(ran[i][j].fst, min(ran[i][j].snd, r));
        j++;
    }
    return ret;
}

struct Rectangle {
    int i1, i2, j1, j2;
    bool operator<(const Rectangle &o) const {
        return make_tuple(i1, i2, j1, j2) < make_tuple(o.i1, o.i2, o.j1, o.j2);
    }
};

map<Rectangle, int> memo;

void expand(Rectangle r, int i, vector<Rectangle> &v) {
    for (auto [j1, j2] : getRanges(i, r.j1, r.j2)) {
        auto [i1, i2] = getMaximal(i, j1, j2);
        v.eb(i1, i2, j1, j2);
    }
}

int dp(Rectangle r) {
    if (memo.count(r)) return memo[r];
    vector<Rectangle> v;
    if (r.i1 > 0) expand(r, r.i1 - 1, v);
    if (r.i2 + 1 < n) expand(r, r.i2 + 1, v);
    int &ret = memo[r];
    for (auto nxt : v) ret = max(ret, dp(nxt) + (nxt.j2 - nxt.j1 + 1) * ((nxt.i2 - nxt.i1 + 1) - (r.i2 - r.i1 + 1)));
    return ret;
}


int biggest_stadium(int N, vector<vi> F) {
    n = N;
    forn(i, n) forn(j, n) pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + F[i][j];
    forn(i, n) {
        forn(j, n) {
            if (F[i][j]) continue;
            if (j == 0 || F[i][j - 1]) {
                ran[i].eb(j, j);
            } else {
                ran[i].back().snd++;
            }
        }
    }
    int ret = 0;
    forn(i, n) for (auto [j1, j2] : ran[i]) {
        auto [i1, i2] = getMaximal(i, j1, j2);
        Rectangle r = {i1, i2, j1, j2};
        ret = max(ret, dp(r) + (j2 - j1 + 1) * (i2 - i1 + 1));
    }
    return ret;
}

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