Submission #1125662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125662		jj_master	Soccer Stadium (IOI23_soccer)	C++20	100 / 100	1610 ms	162648 KiB

soccer

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

#define ll long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ins insert
#define mp make_pair

const int N = 2009;
map<array<int,4>,int> f;
int n, a[N][N], p[N][N], nxt[N][N];

int calc(int li, int ri, int lj, int rj) {
	int l = 1, r = li;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (p[li][rj] - p[li][lj - 1] - p[mid - 1][rj] + p[mid - 1][lj - 1] < 1) r = mid;
		else l = mid + 1;
	}
	if (l < li) return calc(l, ri, lj, rj) + (rj - lj + 1) * (li - l);
	l = ri, r = n;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (p[mid][rj] - p[mid][lj - 1] - p[ri - 1][rj] + p[ri - 1][lj - 1] < 1) l = mid;
		else r = mid - 1;
	}
	if (l > ri) return calc(li, l, lj, rj) + (rj - lj + 1) * (l - ri);
	if (f.count({li, ri, lj, rj})) return f[{li, ri, lj, rj}];
	int crr = 0;
	if (li > 1) {
		for (int j = lj - 1; j < rj; j = nxt[li - 1][j + 1]) {
			if (a[li - 1][j + 1]) continue;
			int l = j + 1, r = min(rj, nxt[li - 1][j + 1] - 1);
			if (l <= r) crr = max(crr, calc(li - 1, ri, l, r) + r - l + 1);
		}
	}
	if (ri < n) {
		for (int j = lj - 1; j < rj; j = nxt[ri + 1][j + 1]) {
			if (a[ri + 1][j + 1]) continue;
			int l = j + 1, r = min(rj, nxt[ri + 1][j + 1] - 1);
			if (l <= r) crr = max(crr, calc(li, ri + 1, l, r) + r - l + 1);
		}
	}
	f[{li, ri, lj, rj}] = crr;
	return crr;
}

int biggest_stadium(int N, vector<vector<int>> w)
{
    n = N;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            a[i][j] = w[i - 1][j - 1];
            p[i][j] = p[i][j - 1] + p[i - 1][j] - p[i - 1][j - 1] + a[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        nxt[i][n + 1] = n + 1;
        for(int j=n;j>=1;j--) {
            if(a[i][j]) nxt[i][j] = j;
            else nxt[i][j] = nxt[i][j + 1];
        }
    }
    int res = 0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<n;j++) {
            if((!j || a[i][j]) && !a[i][j + 1]) {
                res = max(res, calc(i, i, j + 1, nxt[i][j + 1] - 1) + nxt[i][j + 1] - j - 1);
            }
        }
    }
    return res;
}

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