제출 #1064172

#제출 시각아이디문제언어결과실행 시간메모리
1064172AmirAli_H1축구 경기장 (IOI23_soccer)C++17
77.50 / 100
398 ms116852 KiB
// In the name of Allah #include <bits/stdc++.h> #include "soccer.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define F first #define S second #define endl '\n' #define sep ' ' #define pb push_back #define Mp make_pair #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) const int maxn = 2000 + 4; const int oo = 1e9 + 7; int n; int A[maxn][maxn]; vector<pii> ls; int val1[maxn][maxn], val2[maxn][maxn]; pii val[maxn]; int dp[maxn][maxn]; pii valx[maxn][maxn]; bool cmp(pii i, pii j) { return ((i.S - i.F) > (j.S - j.F)); } bool is_ok() { ls.clear(); for (int i = 0; i < n; i++) { int x = 0; for (int j = 0; j < n; j++) { if (A[i][j] != A[i][x]) { if (A[i][x] == 0) ls.pb(Mp(x, j - 1)); x = j; } } if (A[i][x] == 0) ls.pb(Mp(x, n - 1)); } sort(all(ls), cmp); for (int i = 1; i < len(ls); i++) { if (ls[i].F < ls[i - 1].F || ls[i].S > ls[i - 1].S) return 0; } return 1; } int check() { int num = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) num += (A[i][j] == 0); } bool ok = 1; ok &= is_ok(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) swap(A[i][j], A[j][i]); } ok &= is_ok(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) swap(A[i][j], A[j][i]); } if (ok) return num; else return 0; } int get_val(int y) { for (int x = 0; x < n; x++) { if (A[x][y] == 1) val[x] = Mp(n, -1); else val[x] = Mp(val1[x][y], val2[x][y]); } int res = 0; for (int ln = 1; ln <= n; ln++) { for (int l = 0, r = ln - 1; r < n; l++, r++) { if (ln == 1) { valx[l][r] = val[l]; if (valx[l][r].F > valx[l][r].S) dp[l][r] = -oo; else dp[l][r] = (valx[l][r].S - valx[l][r].F + 1); } else { valx[l][r] = val[l]; valx[l][r].F = max(valx[l][r].F, valx[l + 1][r].F); valx[l][r].S = min(valx[l][r].S, valx[l + 1][r].S); if (valx[l][r].F > valx[l][r].S) dp[l][r] = -oo; else dp[l][r] = (valx[l][r].S - valx[l][r].F + 1) + max(dp[l + 1][r], dp[l][r - 1]); } dp[l][r] = max(dp[l][r], -oo); res = max(res, dp[l][r]); } } return res; } int solve() { int mx = 0; for (int j = 0; j < n; j++) { mx = max(mx, get_val(j)); } return mx; } int biggest_stadium(int N, vector<vector<int>> F) { n = N; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { A[i][j] = F[i][j]; if (A[i][j] == 1) ls.pb(Mp(i, j)); } } if (len(ls) == 0) return (n * n); else if (len(ls) == 1) { int i = ls.back().F, j = ls.back().S; return (n * n) - (min(i + 1, n - i) * min(j + 1, n - j)); } for (int i = 0; i < n; i++) { int x = 0; for (int j = 0; j < n; j++) { if (A[i][j] != A[i][x]) x = j; val1[i][j] = x; } x = n - 1; for (int j = n - 1; j >= 0; j--) { if (A[i][j] != A[i][x]) x = j; val2[i][j] = x; } } if (n <= 500) return solve(); else return check(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...