oj.uz

답안 #1059937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1059937 2024-08-15T09:28:51 Z mychecksedad 축구 경기장 (IOI23_soccer) C++17
0 / 100
 245 ms 14684 KB 
#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 biggest_stadium(int n, std::vector<std::vector<int>> a)
{
    int nn = n;
    n += 2;
  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;
        }
      }
    }
  }
  queue<pair<int, int>> q;
  vector<vector<bool>> vis(n, vector<bool>(n));
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i][j] == 0){
        q.push({i, j});
        vis[i][j] = 1;
        break;
      }
    }
    if(q.size()) break;
  }
  int sz = 0;
  while(!q.empty()){
    int x = q.front().ff;
    int y = q.front().ss;
    q.pop();
    for(int i = 0; i < 4; ++i){
      int nx = x + arr[i][0];
      int ny = y + arr[i][1];
      if(nx >= 0 && ny >= 0 && nx < n && ny < n && !vis[nx][ny] && a[nx][ny] == 0){
        vis[nx][ny] = 1;
        q.push({nx, ny});
      }
    }
  }
  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){
            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){
            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 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){
            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){
            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 i = 0; i < n; ++i){
  //   for(int j = 0; j < n; ++j){
  //       cout << pref[i][j] << ' ';
  //   }
  //   cout << '\n';
  // }
  int ans = 0;
  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] + h2[d][l][r][mx]);
          }
          for(int mx = u; mx <= d; ++mx){
            y = max(y, v[l][u][d][mx] + v2[r][u][d][mx]);
          } 
          ans = max(ans, sum + x + y);
        }
      }
    }
  }

  return ans;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:124:7: warning: unused variable 'sz' [-Wunused-variable]
  124 |   int sz = 0;
      |       ^~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14680 KB ok

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14684 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 1 ms 14684 KB ok
4 Correct 2 ms 14684 KB ok
5 Correct 1 ms 6584 KB ok
6 Correct 2 ms 14684 KB ok
7 Runtime error 245 ms 13388 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14684 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 1 ms 14684 KB ok
4 Correct 2 ms 14684 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 1 ms 14684 KB ok
7 Incorrect 1 ms 14684 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14680 KB ok
2 Correct 1 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 1 ms 14684 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 1 ms 14684 KB ok
8 Incorrect 1 ms 14684 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14680 KB ok
2 Correct 1 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 1 ms 14684 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 1 ms 14684 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 1 ms 14684 KB ok
10 Incorrect 1 ms 14684 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14680 KB ok
2 Correct 1 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 1 ms 14684 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 1 ms 14684 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 1 ms 14684 KB ok
10 Incorrect 1 ms 14684 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 14680 KB ok
2 Correct 1 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 1 ms 14684 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 1 ms 6584 KB ok
7 Correct 2 ms 14684 KB ok
8 Runtime error 245 ms 13388 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -