Submission #839832

#	Time	Username	Problem	Language	Result	Execution time	Memory
839832		happypotato	Soccer Stadium (IOI23_soccer)	C++17	12 / 100	4529 ms	3476 KiB

soccer

#include "soccer.h"
 
#include <bits/stdc++.h>
using namespace std;
// #define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
 
int brute(int n, vector<vector<int>> F) {
    int ans = 0;
	bool take[n][n];
    for (int conf = 0; conf < (1 << (n * n)); conf++) {
        bool valid = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                take[i][j] = bool(conf & (1 << (i * n + j)));
				if (take[i][j] && F[i][j]) {
					valid = false;
				}
            }
        }
		if (!valid) continue;
        for (int x = 0; x < n * n; x++) {
            for (int y = 0; y < n * n; y++) {
                int x1 = x / n, x2 = x % n;
                int y1 = y / n, y2 = y % n;
                if (!take[x1][x2] || !take[y1][y2]) continue;
                pii cur; bool can;
                cur = {x1, x2}; can = 1;
                while (cur.ff != y1) {
                    cur.ff += (cur.ff < y1 ? 1 : -1);
                    can &= take[cur.ff][cur.ss];
                }
                while (cur.ss != y2) {
                    cur.ss += (cur.ss < y2 ? 1 : -1);
                    can &= take[cur.ff][cur.ss];
                }
                if (can) continue;
                cur = {x1, x2}; can = 1;
                while (cur.ss != y2) {
                    cur.ss += (cur.ss < y2 ? 1 : -1);
                    can &= take[cur.ff][cur.ss];
                }
                while (cur.ff != y1) {
                    cur.ff += (cur.ff < y1 ? 1 : -1);
                    can &= take[cur.ff][cur.ss];
                }
                if (can) continue;
                valid = false;
                break;
            }
            if (!valid) break;
        }
        if (valid) ans = max(ans, __builtin_popcount(conf));
    }
    return ans;
}
 
bool check(int n, vector<vector<int>> F) {
	bool take[n][n];
	bool valid = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			take[i][j] = (F[i][j] ? 0 : 1);
		}
	}
	for (int x = 0; x < n * n; x++) {
		for (int y = 0; y < n * n; y++) {
			int x1 = x / n, x2 = x % n;
			int y1 = y / n, y2 = y % n;
			if (!take[x1][x2] || !take[y1][y2]) continue;
			pii cur; bool can;
			cur = {x1, x2}; can = 1;
			while (cur.ff != y1) {
				cur.ff += (cur.ff < y1 ? 1 : -1);
				can &= take[cur.ff][cur.ss];
			}
			while (cur.ss != y2) {
				cur.ss += (cur.ss < y2 ? 1 : -1);
				can &= take[cur.ff][cur.ss];
			}
			if (can) continue;
			cur = {x1, x2}; can = 1;
			while (cur.ss != y2) {
				cur.ss += (cur.ss < y2 ? 1 : -1);
				can &= take[cur.ff][cur.ss];
			}
			while (cur.ff != y1) {
				cur.ff += (cur.ff < y1 ? 1 : -1);
				can &= take[cur.ff][cur.ss];
			}
			if (can) continue;
			return false;
		}
	}
	return true;
}
 
const int MIN = -1e9;
int biggest_stadium(int n, vector<vector<int>> F)
{
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cnt += (F[i][j] ? 0 : 1);
		}
	}
	return (check(n, F) ? cnt : 0);
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (F[i][j]) {
				int ans = 0;
				ans = max(ans, i * n + j * n - i * j);
				ans = max(ans, i * n + (n - j - 1) * n - i * (n - j - 1));
				ans = max(ans, (n - i - 1) * n + j * n - (n - i - 1) * j);
				ans = max(ans, (n - i - 1) * n + (n - j - 1) * n - (n - i - 1) * (n - j - 1));
				return ans;
			}
		}
	}
	return n * n;
	if (n <= 3) return brute(n, F);
	if (n > 500) return 0;
	if (n == 1) return (F[0][0] ? 0 : 1);
	if (n == 2) {
		int ans = 4;
		ans -= F[0][0];
		ans -= F[0][1];
		ans -= F[1][0];
		ans -= F[1][1];
		if (F[0][0] && !F[0][1] && !F[1][0] && F[1][1]) ans--;
		if (!F[0][0] && F[0][1] && F[1][0] && !F[1][1]) ans--;
		return ans;
	}
	bool a[n + 1][n + 1];
	int ps[n + 1][n + 1];
	for (int i = 1; i <= n; i++) {
		ps[i][0] = 0;
		for (int j = 1; j <= n; j++) {
			a[i][j] = F[i - 1][j - 1];
			ps[i][j] = ps[i][j - 1] + a[i][j];
		}
	}
	int dp[2][n + 1][n + 1][n + 1]; // dp[vert pos][l range][r range]
	int dpm[2][n + 1][n + 1][n + 1];
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				dp[0][i][j][k] = dp[1][i][j][k] = 0;
				dpm[0][i][j][k] = dpm[1][i][j][k] = 0;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int l = 1; l <= n; l++) {
			for (int r = l; r <= n; r++) {
				if (ps[i][r] - ps[i][l - 1]) {
					dp[0][i][l][r] = 0;
					dp[1][i][l][r] = 0;
				} else {
					dp[0][i][l][r] = dpm[0][i - 1][l][r] + (r - l + 1);
					dp[1][i][l][r] = dpm[1][i - 1][l][r] + (r - l + 1);
				}
			}
		}
		for (int j = 1; j <= n; j++) {
			dpm[0][i][j][j] = dp[0][i][j][j];
		}
		for (int diff = 1; diff < n; diff++) {
			for (int l = 1, r = 1 + diff; r <= n; l++, r++) {
				dpm[0][i][l][r] = max(max(dpm[0][i][l + 1][r], dpm[0][i][l][r - 1]), dp[0][i][l][r]);
			}
		}
		dpm[1][i][1][n] = max(dp[0][i][1][n], dp[1][i][1][n]);
		for (int diff = n - 2; diff >= 0; diff--) {
			for (int l = 1, r = 1 + diff; r <= n; l++, r++) {
				dpm[1][i][l][r] = max(dp[0][i][l][r], dp[1][i][l][r]);
				if (l > 1) {
					dpm[1][i][l][r] = max(dpm[1][i][l][r], dpm[1][i][l - 1][r]);
				}
				if (r < n) {
					dpm[1][i][l][r] = max(dpm[1][i][l][r], dpm[1][i][l][r + 1]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = j; k <= n; k++) {
				// cerr << i << ' ' << j << ' ' << k << ": ";
				// cerr << dp[0][i][j][k] << ", " << dp[1][i][j][k] << " | ";
				// cerr << dpm[0][i][j][k] << ", " << dpm[1][i][j][k] << endl;
				ans = max(ans, dp[0][i][j][k]);
				ans = max(ans, dp[1][i][j][k]);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

soccer.cpp: In function 'bool check(int, std::vector<std::vector<int> >)':
soccer.cpp:64:7: warning: unused variable 'valid' [-Wunused-variable]
   64 |  bool valid = true;
      |       ^~~~~

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