Submission #1060043

#TimeUsernameProblemLanguageResultExecution timeMemory
1060043mychecksedadSoccer Stadium (IOI23_soccer)C++17
8 / 100
211 ms31212 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define ll long long #define ff first #define ss second const int N = 32; int arr[4][2]={ {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; int h[N][N][N][N], v[N][N][N][N], h2[N][N][N][N], v2[N][N][N][N]; int hh[N][N][N][N], vv[N][N][N][N], hh2[N][N][N][N], vv2[N][N][N][N]; int biggest_stadium(int n, std::vector<std::vector<int>> a) { int nn = n; n += n; vector<vector<int>> U(n, vector<int>(n)); vector<vector<int>> U2(n, vector<int>(n)); vector<vector<int>> L(n, vector<int>(n)); vector<vector<int>> L2(n, vector<int>(n)); vector<vector<int>> R2(n, vector<int>(n)); vector<vector<int>> D2(n, vector<int>(n)); vector<vector<int>> pref(n, vector<int>(n)); n =nn; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ pref[i][j] = a[i][j] == 0; if(i > 0) pref[i][j] += pref[i - 1][j]; if(j > 0) pref[i][j] += pref[i][j - 1]; if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1]; if(i == 0){ if(a[i][j] == 1) U[i][j] = i; else U[i][j] = -1; }else{ if(a[i][j] == 1){ if(a[i - 1][j] == 1) U[i][j] = U[i - 1][j]; else U[i][j] = i; }else{ U[i][j] = -1; } } if(j == 0){ if(a[i][j] == 1) L[i][j] = j; else L[i][j] = -1; }else{ if(a[i][j] == 1){ if(a[i][j - 1] == 1) L[i][j] = L[i][j - 1]; else L[i][j] = j; }else{ L[i][j] = -1; } } if(i == 0){ if(a[i][j] == 0) U2[i][j] = i; else U2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i - 1][j] == 0) U2[i][j] = U2[i - 1][j]; else U2[i][j] = i; }else{ U2[i][j] = -1; } } if(j == 0){ if(a[i][j] == 0) L2[i][j] = j; else L2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i][j - 1] == 0) L2[i][j] = L2[i][j - 1]; else L2[i][j] = j; }else{ L2[i][j] = -1; } } } for(int j = n-1; j >= 0; --j){ if(j == n-1){ if(a[i][j] == 0) R2[i][j] = j; else R2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i][j + 1] == 0) R2[i][j] = R2[i][j + 1]; else R2[i][j] = j; }else{ R2[i][j] = -1; } } } } for(int i = n-1; i >= 0; --i){ for(int j = 0; j < n; ++j){ if(i == n-1){ if(a[i][j] == 0) D2[i][j] = i; else D2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i + 1][j] == 0) D2[i][j] = D2[i + 1][j]; else D2[i][j] = i; }else{ D2[i][j] = -1; } } } } for(int row = 0; row < n; ++row){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(U2[row][mx] == -1){ h[row][l][r][mx] = 0; continue; } int cur = row - U2[row][mx], tot = row - U2[row][mx]; for(int i = mx - 1; i >= l; --i){ int szz = row - U2[row][i]; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } cur = row - U2[row][mx]; for(int i = mx + 1; i <= r; ++i){ int szz = row - U2[row][i]; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } h[row][l][r][mx] = tot; } } } } for(int row = 0; row < n; ++row){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(U2[row][mx] == -1){ hh[row][l][r][mx] = 0; continue; } int cur = row - U2[row][mx], tot = row - U2[row][mx]; for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){ int x = mx - dif; int y = mx + dif; int sz = n + 1; int o = 0; if(x >= l) sz = min(sz, row - U2[row][x]),++o; if(y <= r) sz = min(sz, row - U2[row][y]),++o; if(sz >= cur){ tot += cur*o; }else{ tot += sz*o; cur = min(cur, sz); } } hh[row][l][r][mx] = tot; } } } } for(int row = 0; row < n; ++row){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(D2[row][mx] == -1){ h2[row][l][r][mx] = 0; continue; } int cur = D2[row][mx] - row, tot = D2[row][mx] - row; for(int i = mx - 1; i >= l; --i){ int szz = D2[row][i] - row; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } cur = D2[row][mx] - row; for(int i = mx + 1; i <= r; ++i){ int szz = D2[row][i] - row; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } h2[row][l][r][mx] = tot; } } } } for(int row = 0; row < n; ++row){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(D2[row][mx] == -1){ hh2[row][l][r][mx] = 0; continue; } int cur = D2[row][mx] - row, tot = D2[row][mx] - row; for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){ int x = mx - dif; int y = mx + dif; int sz = n + 1; int o = 0; if(x >= l) sz = min(sz, D2[row][x] - row),++o; if(y <= r) sz = min(sz, D2[row][y] - row),++o; if(sz >= cur){ tot += cur*o; }else{ tot += sz*o; cur = min(cur, sz); } } hh2[row][l][r][mx] = tot; } } } } for(int col = 0; col < n; ++col){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(L2[col][mx] == -1){ v[col][l][r][mx] = 0; continue; } int cur = col - L2[mx][col] , tot = col - L2[mx][col]; for(int i = mx - 1; i >= l; --i){ int szz = col - L2[i][col] ; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } cur = col - L2[mx][col] ; for(int i = mx + 1; i <= r; ++i){ int szz = col - L2[i][col]; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } v[col][l][r][mx] = tot; } } } } for(int col = 0; col < n; ++col){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(L2[col][mx] == -1){ vv[col][l][r][mx] = 0; continue; } int cur = col - L2[mx][col], tot = col - L2[mx][col]; for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){ int x = mx - dif; int y = mx + dif; int sz = n + 1; int o = 0; if(x >= l) sz = min(sz, col - L2[x][col]), ++o; if(y <= r) sz = min(sz, col - L2[y][col]), ++o; if(sz >= cur){ tot += cur*o; }else{ tot += o*sz; cur = min(cur, sz); } } vv[col][l][r][mx] = tot; } } } } for(int col = 0; col < n; ++col){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(R2[col][mx] == -1){ v2[col][l][r][mx] = 0; continue; } int cur = R2[mx][col] - col , tot = R2[mx][col] - col; for(int i = mx - 1; i >= l; --i){ int szz = R2[i][col] - col; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } cur = R2[mx][col] - col; for(int i = mx + 1; i <= r; ++i){ int szz = R2[i][col] - col; if(szz >= cur){ tot += cur; }else{ tot += szz; cur = min(cur, szz); } } v2[col][l][r][mx] = tot; } } } } for(int col = 0; col < n; ++col){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int mx = l; mx <= r; ++mx){ if(R2[col][mx] == -1){ vv2[col][l][r][mx] = 0; continue; } int cur = R2[mx][col]-col, tot =R2[mx][col]-col; for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){ int x = mx - dif; int y = mx + dif; int sz = n + 1; int o = 0; if(x >= l) sz = min(sz, R2[x][col]-col ), o++; if(y <= r) sz = min(sz, R2[y][col]-col), o++; if(sz >= cur){ tot += cur * o; }else{ tot += sz * o; cur = min(cur, sz); } } vv2[col][l][r][mx] = tot; } } } } // for(int i = 0; i < n; ++i){ // for(int j = 0; j < n; ++j){ // cout << pref[i][j] << ' '; // } // cout << '\n'; // } int ans = 1; for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ for(int u = 0; u < n; ++u){ for(int d = u; d < n; ++d){ int sum = pref[d][r]; if(u > 0) sum -= pref[u - 1][r]; if(l > 0) sum -= pref[d][l - 1]; if(u > 0 && l > 0) sum += pref[u - 1][l - 1]; if(sum != (r - l + 1) * (d - u + 1)) continue; // cout << l << ' ' << r << ' ' << u << ' ' << d << ' ' << (r - l + 1) * (d - u + 1) << '\n'; int x = 0, y = 0; for(int mx = l; mx <= r; ++mx){ x = max(x, h[u][l][r][mx] + hh2[d][l][r][mx]); x = max(x, hh[u][l][r][mx] + hh2[d][l][r][mx]); x = max(x, hh[u][l][r][mx] + h2[d][l][r][mx]); } for(int mx = u; mx <= d; ++mx){ y = max(y, v[l][u][d][mx] + vv2[r][u][d][mx]); y = max(y, vv[l][u][d][mx] + v2[r][u][d][mx]); y = max(y, vv[l][u][d][mx] + vv2[r][u][d][mx]); } // if(sum + x + y > ans){ // cout << l << ' ' << r<< ' ' << u << ' ' << d <<' ' << sum + x + y << ' ' << sum << ' ' << x << ' ' << y << '\n'; // } ans = max(ans, sum + x + y); // cout << l << ' ' << r<< ' ' << u << ' ' << d <<' ' << sum + x + y << ' ' << sum << ' ' << x << ' ' << y << '\n'; } } } } return ans; }
#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...