oj.uz

Submission #963964

# Submission time Handle Problem Language Result Execution time Memory
963964 2024-04-16T05:57:31 Z nguyentunglam Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1 ms 2392 KB 
#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 2010;

int n;

bool a[N][N];

vector<int> arr[N];

int check_valid() {
  for(int col = 0; col < n; col++) {
    for(int row = 0; row < n; row++) if (a[row][col] == 0) arr[col].push_back(row);
  }

  int st = 0;
  while (st < n && arr[st].empty()) st++;
  if (st == n) return 0;
  int ed = st;

  while (ed < n && !arr[ed].empty()) ed++; ed--;
  for(int i = 1; i < st; i++) if (!arr[i].empty()) return 0;
  for(int i = ed + 1; i < n; i++) if (!arr[i].empty()) return 0;
  for(int i = st; i <= ed; i++) if (arr[i].size() != arr[i].back() - arr[i][0] + 1) return 0;

  int cnt = 0;

  for(int i = st; i <= ed; i++) cnt += arr[i].size();

  int L = max(arr[st][0], arr[ed][0]);
  int R = min(arr[st].back(), arr[ed].back());
  while (st <= ed) {
    if (arr[st].size() <= arr[ed].size()) {
      if (arr[st][0] <= L && arr[st].back() >= R) {
        L = arr[st][0];
        R = arr[st].back();
        st++;
      }
      else return 0;
    }
    else {
      if (arr[ed][0] <= L && arr[ed].back() >= R) {
        L = arr[ed][0];
        R = arr[ed].back();
        ed--;
      }
      else return 0;
    }
  }
  return cnt;
}

namespace sub4 {
const int N = 51;
int pref[N][N];
int dp[N][N][N][N];
int solve() {
  for(int i = 0; i < n; i++) {
    pref[i][0] = a[i][0];
    for(int j = 1; j < n; j++) pref[i][j] = pref[i][j - 1] + a[i][j];
  }

  auto check = [&] (int i, int l, int r) {
    int sum = pref[i][r];
    if (l > 0) sum -= pref[i][l - 1];
    return sum == 0;
  };

  int ans = 0;

  for(int x = n - 1; x >= 0; x--) for(int y = x - 1; y <= n; y++) {
    for(int u = 0; u < n; u++) for(int v = u; v < n; v++) {
      for(int _u = 0; _u <= u; _u++) for(int _v = v; _v < n; _v++) {
        if (y + 1 < n && check(y + 1, u, v)) dp[x][y + 1][u][v] = max(dp[x][y + 1][u][v], dp[x][y][_u][_v] + v - u + 1);
        if (x > 0 && check(x - 1, u, v)) dp[x - 1][y][u][v] = max(dp[x - 1][y][u][v], dp[x][y][_u][_v] + v - u + 1);
      }
//      cout << dp[x][y][u][v] << endl;
      ans = max(ans, dp[x][y][u][v]);
    }
  }

//  cout << ans << endl;

  return ans;
}
}

namespace sub5 {
int solve() {
  return 0;
}
}


int biggest_stadium(int N, std::vector<std::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 (n <= 30) return sub4::solve();
  if (n <= 500) return sub5::solve();
  return check_valid();
}

#ifdef ngu
int main()
{
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}
#endif // ngu

Compilation message

soccer.cpp: In function 'int check_valid()':
soccer.cpp:23:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   23 |   while (ed < n && !arr[ed].empty()) ed++; ed--;
      |   ^~~~~
soccer.cpp:23:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   23 |   while (ed < n && !arr[ed].empty()) ed++; ed--;
      |                                            ^~
soccer.cpp:26:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   26 |   for(int i = st; i <= ed; i++) if (arr[i].size() != arr[i].back() - arr[i][0] + 1) return 0;
      |                                     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2392 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB wrong
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB wrong
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2392 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2392 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2392 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2392 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -