Submission #1060043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060043		mychecksedad	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	211 ms	31212 KiB

soccer

#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;
}

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