oj.uz

Submission #964432

# Submission time Handle Problem Language Result Execution time Memory
964432 2024-04-16T20:16:21 Z nguyentunglam Soccer Stadium (IOI23_soccer) C++17
100 / 100
 4473 ms 690368 KB 
#include "soccer.h"
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
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 AC {
const int N = 2010, M = 2e3 * 2e3 * 2 + 10;

int b[N], L[N], R[N], dp[M], trans[2][M];

int close[2][N][N];

vector<int> open[2][N][N], lst[N];

tuple<int, int, int, int> rect[M];

int solve() {

//  for(int i = 1; i <= n; i++) {
//    for(int j = 1; j <= n; j++) cout << a[i][j] << " "; cout << endl;
//  }
  int m = 0;

  auto histogram = [&] () {
    stack<int> st;
    for(int i = 1; i <= n; i++) {
      while (!st.empty() && b[st.top()] >= b[i]) st.pop();
      L[i] = st.empty() ? 0 : st.top();
      st.push(i);
    }
    while (!st.empty()) st.pop();
    for(int i = n; i >= 1; i--) {
      while (!st.empty() && b[st.top()] >= b[i]) st.pop();
      R[i] = st.empty() ? n + 1 : st.top();
      st.push(i);
    }
  };

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      if (a[i][j]) b[j] = 0;
      else b[j]++;
    }
    histogram();
    for(int j = 1; j <= n; j++) if (b[j]) {
      rect[++m] = make_tuple(i - b[j] + 1, i, L[j] + 1, R[j] - 1);
    }
  }

  for(int j = 1; j <= n; j++) b[j] = 0;

  for(int i = n; i >= 1; i--) {
    for(int j = 1; j <= n; j++) {
      if (a[i][j]) b[j] = 0;
      else b[j]++;
    }
    histogram();
    for(int j = 1; j <= n; j++) if (b[j]) {
      rect[++m] = make_tuple(i, i + b[j] - 1, L[j] + 1, R[j] - 1);
    }
  }

  for(int i = 1; i <= m; i++) {
    lst[get<1> (rect[i]) - get<0> (rect[i])].push_back(i);
  }

  for(int delta = 0; delta < n; delta++) {
    for(int &i : lst[delta]) {
      int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i];
      open[0][x2][y1].emplace_back(i);
      close[0][x2][y2]++;
      open[1][x1][y1].emplace_back(i);
      close[1][x1][y2]++;
    }
  }

  for(int i = 1; i <= n; i++) for(int t = 0; t < 2; t++) {
    stack<int> st;
    for(int j = 1; j <= n; j++) {
      for(auto &k : open[t][i][j]) {
        trans[t][k] = st.empty() ? 0 : st.top();
        st.push(k);
      }
      while (close[t][i][j]--) st.pop();
    }
  }

  int ans = 0;

  for(int delta = 0; delta < n; delta++) {
    for(int &i : lst[delta]) {
      int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i];
      dp[i] = (x2 - x1 + 1) * (y2 - y1 + 1);
      if (trans[0][i]) { // top
        int j = trans[0][i];
        dp[i] = max(dp[i], dp[j] + (get<0> (rect[j]) - x1) * (y2 - y1 + 1));
      } // bottom
      if (trans[1][i]) {
        int j = trans[1][i];
        dp[i] = max(dp[i], dp[j] + (x2 - get<1> (rect[j])) * (y2 - y1 + 1));
      }
      ans = max(ans, dp[i]);
    }
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

  return ans;
}
}


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();
  for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = F[i - 1][j - 1];
  return AC::solve();
}

#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:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   24 |   while (ed < n && !arr[ed].empty()) ed++; ed--;
      |   ^~~~~
soccer.cpp:24:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   24 |   while (ed < n && !arr[ed].empty()) ed++; ed--;
      |                                            ^~
soccer.cpp:27: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]
   27 |   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 139 ms 203344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 203344 KB ok
2 Correct 49 ms 203348 KB ok
3 Correct 45 ms 205520 KB ok
4 Correct 47 ms 203344 KB ok
5 Correct 45 ms 203428 KB ok
6 Correct 45 ms 203348 KB ok
7 Correct 49 ms 206240 KB ok
8 Correct 91 ms 237676 KB ok
9 Correct 749 ms 597252 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 203344 KB ok
2 Correct 49 ms 203348 KB ok
3 Correct 46 ms 203544 KB ok
4 Correct 48 ms 203348 KB ok
5 Correct 45 ms 203480 KB ok
6 Correct 47 ms 205396 KB ok
7 Correct 47 ms 203416 KB ok
8 Correct 45 ms 203568 KB ok
9 Correct 46 ms 203428 KB ok
10 Correct 45 ms 203568 KB ok
11 Correct 45 ms 203344 KB ok
12 Correct 47 ms 203344 KB ok
13 Correct 48 ms 205404 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 203344 KB ok
2 Correct 47 ms 203344 KB ok
3 Correct 49 ms 203348 KB ok
4 Correct 46 ms 203544 KB ok
5 Correct 48 ms 203348 KB ok
6 Correct 45 ms 203480 KB ok
7 Correct 47 ms 205396 KB ok
8 Correct 47 ms 203416 KB ok
9 Correct 45 ms 203568 KB ok
10 Correct 46 ms 203428 KB ok
11 Correct 45 ms 203568 KB ok
12 Correct 45 ms 203344 KB ok
13 Correct 47 ms 203344 KB ok
14 Correct 48 ms 205404 KB ok
15 Correct 50 ms 203344 KB ok
16 Correct 48 ms 203348 KB ok
17 Correct 45 ms 203612 KB ok
18 Correct 52 ms 203512 KB ok
19 Correct 45 ms 203468 KB ok
20 Correct 45 ms 205528 KB ok
21 Correct 48 ms 205588 KB ok
22 Correct 45 ms 205496 KB ok
23 Correct 45 ms 205392 KB ok
24 Correct 48 ms 205392 KB ok
25 Correct 47 ms 205488 KB ok
26 Correct 45 ms 203556 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 203344 KB ok
2 Correct 47 ms 203344 KB ok
3 Correct 49 ms 203348 KB ok
4 Correct 45 ms 205520 KB ok
5 Correct 47 ms 203344 KB ok
6 Correct 46 ms 203544 KB ok
7 Correct 48 ms 203348 KB ok
8 Correct 45 ms 203480 KB ok
9 Correct 47 ms 205396 KB ok
10 Correct 47 ms 203416 KB ok
11 Correct 45 ms 203568 KB ok
12 Correct 46 ms 203428 KB ok
13 Correct 45 ms 203568 KB ok
14 Correct 45 ms 203344 KB ok
15 Correct 47 ms 203344 KB ok
16 Correct 48 ms 205404 KB ok
17 Correct 50 ms 203344 KB ok
18 Correct 48 ms 203348 KB ok
19 Correct 45 ms 203612 KB ok
20 Correct 52 ms 203512 KB ok
21 Correct 45 ms 203468 KB ok
22 Correct 45 ms 205528 KB ok
23 Correct 48 ms 205588 KB ok
24 Correct 45 ms 205496 KB ok
25 Correct 45 ms 205392 KB ok
26 Correct 48 ms 205392 KB ok
27 Correct 47 ms 205488 KB ok
28 Correct 45 ms 203556 KB ok
29 Correct 49 ms 205552 KB ok
30 Correct 46 ms 203516 KB ok
31 Correct 46 ms 203600 KB ok
32 Correct 51 ms 203604 KB ok
33 Correct 47 ms 205596 KB ok
34 Correct 46 ms 205392 KB ok
35 Correct 48 ms 205648 KB ok
36 Correct 46 ms 205400 KB ok
37 Correct 46 ms 205396 KB ok
38 Correct 46 ms 205648 KB ok
39 Correct 47 ms 205428 KB ok
40 Correct 48 ms 203628 KB ok
41 Correct 47 ms 203528 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 203344 KB ok
2 Correct 47 ms 203344 KB ok
3 Correct 49 ms 203348 KB ok
4 Correct 45 ms 205520 KB ok
5 Correct 47 ms 203344 KB ok
6 Correct 46 ms 203544 KB ok
7 Correct 48 ms 203348 KB ok
8 Correct 45 ms 203480 KB ok
9 Correct 47 ms 205396 KB ok
10 Correct 47 ms 203416 KB ok
11 Correct 45 ms 203568 KB ok
12 Correct 46 ms 203428 KB ok
13 Correct 45 ms 203568 KB ok
14 Correct 45 ms 203344 KB ok
15 Correct 47 ms 203344 KB ok
16 Correct 48 ms 205404 KB ok
17 Correct 50 ms 203344 KB ok
18 Correct 48 ms 203348 KB ok
19 Correct 45 ms 203612 KB ok
20 Correct 52 ms 203512 KB ok
21 Correct 45 ms 203468 KB ok
22 Correct 45 ms 205528 KB ok
23 Correct 48 ms 205588 KB ok
24 Correct 45 ms 205496 KB ok
25 Correct 45 ms 205392 KB ok
26 Correct 48 ms 205392 KB ok
27 Correct 47 ms 205488 KB ok
28 Correct 45 ms 203556 KB ok
29 Correct 49 ms 205552 KB ok
30 Correct 46 ms 203516 KB ok
31 Correct 46 ms 203600 KB ok
32 Correct 51 ms 203604 KB ok
33 Correct 47 ms 205596 KB ok
34 Correct 46 ms 205392 KB ok
35 Correct 48 ms 205648 KB ok
36 Correct 46 ms 205400 KB ok
37 Correct 46 ms 205396 KB ok
38 Correct 46 ms 205648 KB ok
39 Correct 47 ms 205428 KB ok
40 Correct 48 ms 203628 KB ok
41 Correct 47 ms 203528 KB ok
42 Correct 205 ms 239904 KB ok
43 Correct 182 ms 236740 KB ok
44 Correct 203 ms 243040 KB ok
45 Correct 167 ms 242476 KB ok
46 Correct 235 ms 242836 KB ok
47 Correct 88 ms 237724 KB ok
48 Correct 95 ms 229560 KB ok
49 Correct 93 ms 229404 KB ok
50 Correct 93 ms 239680 KB ok
51 Correct 117 ms 239748 KB ok
52 Correct 83 ms 221772 KB ok
53 Correct 71 ms 219800 KB ok
54 Correct 73 ms 218140 KB ok
55 Correct 85 ms 222728 KB ok
56 Correct 81 ms 221620 KB ok
57 Correct 108 ms 241160 KB ok
58 Correct 123 ms 241952 KB ok
59 Correct 127 ms 242224 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 203344 KB ok
2 Correct 47 ms 203344 KB ok
3 Correct 49 ms 203348 KB ok
4 Correct 45 ms 205520 KB ok
5 Correct 47 ms 203344 KB ok
6 Correct 45 ms 203428 KB ok
7 Correct 45 ms 203348 KB ok
8 Correct 49 ms 206240 KB ok
9 Correct 91 ms 237676 KB ok
10 Correct 749 ms 597252 KB ok
11 Correct 46 ms 203544 KB ok
12 Correct 48 ms 203348 KB ok
13 Correct 45 ms 203480 KB ok
14 Correct 47 ms 205396 KB ok
15 Correct 47 ms 203416 KB ok
16 Correct 45 ms 203568 KB ok
17 Correct 46 ms 203428 KB ok
18 Correct 45 ms 203568 KB ok
19 Correct 45 ms 203344 KB ok
20 Correct 47 ms 203344 KB ok
21 Correct 48 ms 205404 KB ok
22 Correct 50 ms 203344 KB ok
23 Correct 48 ms 203348 KB ok
24 Correct 45 ms 203612 KB ok
25 Correct 52 ms 203512 KB ok
26 Correct 45 ms 203468 KB ok
27 Correct 45 ms 205528 KB ok
28 Correct 48 ms 205588 KB ok
29 Correct 45 ms 205496 KB ok
30 Correct 45 ms 205392 KB ok
31 Correct 48 ms 205392 KB ok
32 Correct 47 ms 205488 KB ok
33 Correct 45 ms 203556 KB ok
34 Correct 49 ms 205552 KB ok
35 Correct 46 ms 203516 KB ok
36 Correct 46 ms 203600 KB ok
37 Correct 51 ms 203604 KB ok
38 Correct 47 ms 205596 KB ok
39 Correct 46 ms 205392 KB ok
40 Correct 48 ms 205648 KB ok
41 Correct 46 ms 205400 KB ok
42 Correct 46 ms 205396 KB ok
43 Correct 46 ms 205648 KB ok
44 Correct 47 ms 205428 KB ok
45 Correct 48 ms 203628 KB ok
46 Correct 47 ms 203528 KB ok
47 Correct 205 ms 239904 KB ok
48 Correct 182 ms 236740 KB ok
49 Correct 203 ms 243040 KB ok
50 Correct 167 ms 242476 KB ok
51 Correct 235 ms 242836 KB ok
52 Correct 88 ms 237724 KB ok
53 Correct 95 ms 229560 KB ok
54 Correct 93 ms 229404 KB ok
55 Correct 93 ms 239680 KB ok
56 Correct 117 ms 239748 KB ok
57 Correct 83 ms 221772 KB ok
58 Correct 71 ms 219800 KB ok
59 Correct 73 ms 218140 KB ok
60 Correct 85 ms 222728 KB ok
61 Correct 81 ms 221620 KB ok
62 Correct 108 ms 241160 KB ok
63 Correct 123 ms 241952 KB ok
64 Correct 127 ms 242224 KB ok
65 Correct 3225 ms 652648 KB ok
66 Correct 931 ms 410116 KB ok
67 Correct 543 ms 323984 KB ok
68 Correct 2841 ms 672680 KB ok
69 Correct 4473 ms 690368 KB ok
70 Correct 4206 ms 688540 KB ok
71 Correct 2199 ms 653480 KB ok
72 Correct 726 ms 597344 KB ok
73 Correct 955 ms 467000 KB ok
74 Correct 971 ms 471828 KB ok
75 Correct 987 ms 468068 KB ok
76 Correct 754 ms 620300 KB ok
77 Correct 821 ms 620292 KB ok
78 Correct 1420 ms 633596 KB ok
79 Correct 504 ms 297924 KB ok
80 Correct 530 ms 297928 KB ok
81 Correct 632 ms 320108 KB ok
82 Correct 1088 ms 376620 KB ok
83 Correct 838 ms 362264 KB ok
84 Correct 443 ms 310400 KB ok
85 Correct 409 ms 296332 KB ok
86 Correct 525 ms 327528 KB ok
87 Correct 570 ms 332304 KB ok
88 Correct 645 ms 418612 KB ok
89 Correct 661 ms 570404 KB ok
90 Correct 602 ms 510704 KB ok
91 Correct 703 ms 556280 KB ok
92 Correct 614 ms 323524 KB ok
93 Correct 651 ms 325348 KB ok
94 Correct 478 ms 305124 KB ok
95 Correct 452 ms 308056 KB ok
96 Correct 450 ms 306952 KB ok
97 Correct 413 ms 307892 KB ok
98 Correct 421 ms 290560 KB ok
99 Correct 1695 ms 664788 KB ok
100 Correct 1353 ms 655716 KB ok
101 Correct 1356 ms 659868 KB ok
102 Correct 1317 ms 655928 KB ok
103 Correct 1429 ms 668300 KB ok
104 Correct 1460 ms 671604 KB ok
105 Correct 1470 ms 672148 KB ok
106 Correct 1555 ms 673448 KB ok
107 Correct 1581 ms 675012 KB ok
108 Correct 1107 ms 593360 KB ok
109 Correct 1224 ms 597300 KB ok