oj.uz

Submission #963969

# Submission time Handle Problem Language Result Execution time Memory
963969 2024-04-16T06:07:49 Z nguyentunglam Soccer Stadium (IOI23_soccer) C++17
49.5 / 100
 292 ms 59980 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;

//  cout << check(1, 1, 2) << endl;

  memset(dp, -61, sizeof(dp));
  for(int i = 0; i < n; i++) {
    for(int u = 0; u < n; u++) for(int v = u; v < n; v++) if (check(i, u, v)) dp[i][i][u][v] = v - u + 1;
  }

  for(int x = n - 1; x >= 0; x--) for(int y = x; 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);
      }
      ans = max(ans, dp[x][y][u][v]);
    }
  }

  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 Correct 10 ms 26932 KB ok

Subtask #1
1.5 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26912 KB ok
2 Correct 10 ms 26972 KB ok
3 Correct 10 ms 26780 KB ok
4 Correct 10 ms 26976 KB ok
5 Correct 10 ms 26976 KB ok
6 Correct 11 ms 26968 KB ok
7 Partially correct 1 ms 600 KB partial
8 Partially correct 16 ms 3912 KB partial
9 Partially correct 292 ms 59980 KB partial

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26912 KB ok
2 Correct 10 ms 26972 KB ok
3 Correct 9 ms 26800 KB ok
4 Correct 10 ms 26972 KB ok
5 Correct 12 ms 26828 KB ok
6 Correct 11 ms 26972 KB ok
7 Correct 10 ms 26976 KB ok
8 Correct 10 ms 26932 KB ok
9 Correct 9 ms 26972 KB ok
10 Correct 9 ms 26972 KB ok
11 Correct 10 ms 26972 KB ok
12 Correct 10 ms 26972 KB ok
13 Correct 10 ms 27224 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26932 KB ok
2 Correct 9 ms 26912 KB ok
3 Correct 10 ms 26972 KB ok
4 Correct 9 ms 26800 KB ok
5 Correct 10 ms 26972 KB ok
6 Correct 12 ms 26828 KB ok
7 Correct 11 ms 26972 KB ok
8 Correct 10 ms 26976 KB ok
9 Correct 10 ms 26932 KB ok
10 Correct 9 ms 26972 KB ok
11 Correct 9 ms 26972 KB ok
12 Correct 10 ms 26972 KB ok
13 Correct 10 ms 26972 KB ok
14 Correct 10 ms 27224 KB ok
15 Correct 9 ms 26972 KB ok
16 Correct 10 ms 26972 KB ok
17 Correct 9 ms 26968 KB ok
18 Correct 10 ms 26972 KB ok
19 Correct 10 ms 26972 KB ok
20 Correct 10 ms 27128 KB ok
21 Correct 12 ms 26968 KB ok
22 Correct 9 ms 26972 KB ok
23 Correct 11 ms 27004 KB ok
24 Correct 10 ms 26840 KB ok
25 Correct 10 ms 26972 KB ok
26 Correct 10 ms 26764 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26932 KB ok
2 Correct 9 ms 26912 KB ok
3 Correct 10 ms 26972 KB ok
4 Correct 10 ms 26780 KB ok
5 Correct 10 ms 26976 KB ok
6 Correct 9 ms 26800 KB ok
7 Correct 10 ms 26972 KB ok
8 Correct 12 ms 26828 KB ok
9 Correct 11 ms 26972 KB ok
10 Correct 10 ms 26976 KB ok
11 Correct 10 ms 26932 KB ok
12 Correct 9 ms 26972 KB ok
13 Correct 9 ms 26972 KB ok
14 Correct 10 ms 26972 KB ok
15 Correct 10 ms 26972 KB ok
16 Correct 10 ms 27224 KB ok
17 Correct 9 ms 26972 KB ok
18 Correct 10 ms 26972 KB ok
19 Correct 9 ms 26968 KB ok
20 Correct 10 ms 26972 KB ok
21 Correct 10 ms 26972 KB ok
22 Correct 10 ms 27128 KB ok
23 Correct 12 ms 26968 KB ok
24 Correct 9 ms 26972 KB ok
25 Correct 11 ms 27004 KB ok
26 Correct 10 ms 26840 KB ok
27 Correct 10 ms 26972 KB ok
28 Correct 10 ms 26764 KB ok
29 Correct 9 ms 26968 KB ok
30 Correct 72 ms 26792 KB ok
31 Correct 57 ms 26972 KB ok
32 Correct 48 ms 27016 KB ok
33 Correct 46 ms 26968 KB ok
34 Correct 52 ms 26972 KB ok
35 Correct 57 ms 26972 KB ok
36 Correct 44 ms 26972 KB ok
37 Correct 51 ms 26796 KB ok
38 Correct 51 ms 27016 KB ok
39 Correct 53 ms 26968 KB ok
40 Correct 69 ms 26972 KB ok
41 Correct 73 ms 27020 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26932 KB ok
2 Correct 9 ms 26912 KB ok
3 Correct 10 ms 26972 KB ok
4 Correct 10 ms 26780 KB ok
5 Correct 10 ms 26976 KB ok
6 Correct 9 ms 26800 KB ok
7 Correct 10 ms 26972 KB ok
8 Correct 12 ms 26828 KB ok
9 Correct 11 ms 26972 KB ok
10 Correct 10 ms 26976 KB ok
11 Correct 10 ms 26932 KB ok
12 Correct 9 ms 26972 KB ok
13 Correct 9 ms 26972 KB ok
14 Correct 10 ms 26972 KB ok
15 Correct 10 ms 26972 KB ok
16 Correct 10 ms 27224 KB ok
17 Correct 9 ms 26972 KB ok
18 Correct 10 ms 26972 KB ok
19 Correct 9 ms 26968 KB ok
20 Correct 10 ms 26972 KB ok
21 Correct 10 ms 26972 KB ok
22 Correct 10 ms 27128 KB ok
23 Correct 12 ms 26968 KB ok
24 Correct 9 ms 26972 KB ok
25 Correct 11 ms 27004 KB ok
26 Correct 10 ms 26840 KB ok
27 Correct 10 ms 26972 KB ok
28 Correct 10 ms 26764 KB ok
29 Correct 9 ms 26968 KB ok
30 Correct 72 ms 26792 KB ok
31 Correct 57 ms 26972 KB ok
32 Correct 48 ms 27016 KB ok
33 Correct 46 ms 26968 KB ok
34 Correct 52 ms 26972 KB ok
35 Correct 57 ms 26972 KB ok
36 Correct 44 ms 26972 KB ok
37 Correct 51 ms 26796 KB ok
38 Correct 51 ms 27016 KB ok
39 Correct 53 ms 26968 KB ok
40 Correct 69 ms 26972 KB ok
41 Correct 73 ms 27020 KB ok
42 Partially correct 16 ms 3784 KB partial
43 Partially correct 16 ms 3928 KB partial
44 Partially correct 18 ms 3932 KB partial
45 Partially correct 17 ms 4184 KB partial
46 Partially correct 16 ms 3920 KB partial
47 Partially correct 16 ms 3792 KB partial
48 Incorrect 16 ms 3932 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26932 KB ok
2 Correct 9 ms 26912 KB ok
3 Correct 10 ms 26972 KB ok
4 Correct 10 ms 26780 KB ok
5 Correct 10 ms 26976 KB ok
6 Correct 10 ms 26976 KB ok
7 Correct 11 ms 26968 KB ok
8 Partially correct 1 ms 600 KB partial
9 Partially correct 16 ms 3912 KB partial
10 Partially correct 292 ms 59980 KB partial
11 Correct 9 ms 26800 KB ok
12 Correct 10 ms 26972 KB ok
13 Correct 12 ms 26828 KB ok
14 Correct 11 ms 26972 KB ok
15 Correct 10 ms 26976 KB ok
16 Correct 10 ms 26932 KB ok
17 Correct 9 ms 26972 KB ok
18 Correct 9 ms 26972 KB ok
19 Correct 10 ms 26972 KB ok
20 Correct 10 ms 26972 KB ok
21 Correct 10 ms 27224 KB ok
22 Correct 9 ms 26972 KB ok
23 Correct 10 ms 26972 KB ok
24 Correct 9 ms 26968 KB ok
25 Correct 10 ms 26972 KB ok
26 Correct 10 ms 26972 KB ok
27 Correct 10 ms 27128 KB ok
28 Correct 12 ms 26968 KB ok
29 Correct 9 ms 26972 KB ok
30 Correct 11 ms 27004 KB ok
31 Correct 10 ms 26840 KB ok
32 Correct 10 ms 26972 KB ok
33 Correct 10 ms 26764 KB ok
34 Correct 9 ms 26968 KB ok
35 Correct 72 ms 26792 KB ok
36 Correct 57 ms 26972 KB ok
37 Correct 48 ms 27016 KB ok
38 Correct 46 ms 26968 KB ok
39 Correct 52 ms 26972 KB ok
40 Correct 57 ms 26972 KB ok
41 Correct 44 ms 26972 KB ok
42 Correct 51 ms 26796 KB ok
43 Correct 51 ms 27016 KB ok
44 Correct 53 ms 26968 KB ok
45 Correct 69 ms 26972 KB ok
46 Correct 73 ms 27020 KB ok
47 Partially correct 16 ms 3784 KB partial
48 Partially correct 16 ms 3928 KB partial
49 Partially correct 18 ms 3932 KB partial
50 Partially correct 17 ms 4184 KB partial
51 Partially correct 16 ms 3920 KB partial
52 Partially correct 16 ms 3792 KB partial
53 Incorrect 16 ms 3932 KB wrong
54 Halted 0 ms 0 KB -