oj.uz

Submission #964434

# Submission time Handle Problem Language Result Execution time Memory
964434 2024-04-16T20:25:46 Z nguyentunglam Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2102 ms 418012 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[N];

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

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

int solve() {
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
//  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);
  }

  cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

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

  cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  for(int i = 1; i <= n; i++) for(int t = 0; t < 2; t++) {
    for(auto &j : event[t][i]) {
      int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[j];
      open[y1].push_back(j);
      close[y2]++;
    }

    stack<int> st;

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

  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 2 ms 10584 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 2 ms 10588 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 10588 KB ok
5 Correct 2 ms 10744 KB ok
6 Correct 2 ms 10588 KB ok
7 Correct 4 ms 13404 KB ok
8 Correct 54 ms 37644 KB ok
9 Correct 785 ms 387640 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 2 ms 10588 KB ok
3 Correct 2 ms 10584 KB ok
4 Correct 2 ms 10588 KB ok
5 Correct 2 ms 10584 KB ok
6 Correct 2 ms 12632 KB ok
7 Correct 2 ms 10720 KB ok
8 Correct 2 ms 10584 KB ok
9 Correct 2 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 2 ms 10740 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 2 ms 12632 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 2 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 2 ms 10584 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 2 ms 12632 KB ok
8 Correct 2 ms 10720 KB ok
9 Correct 2 ms 10584 KB ok
10 Correct 2 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 2 ms 10740 KB ok
13 Correct 2 ms 10588 KB ok
14 Correct 2 ms 12632 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 2 ms 10588 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 2 ms 12716 KB ok
21 Correct 2 ms 12636 KB ok
22 Correct 2 ms 12636 KB ok
23 Correct 2 ms 12632 KB ok
24 Correct 2 ms 12632 KB ok
25 Correct 2 ms 12636 KB ok
26 Correct 2 ms 10844 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 2 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 2 ms 10588 KB ok
8 Correct 2 ms 10584 KB ok
9 Correct 2 ms 12632 KB ok
10 Correct 2 ms 10720 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 2 ms 10740 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 2 ms 12632 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 2 ms 10588 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 2 ms 10588 KB ok
22 Correct 2 ms 12716 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12636 KB ok
25 Correct 2 ms 12632 KB ok
26 Correct 2 ms 12632 KB ok
27 Correct 2 ms 12636 KB ok
28 Correct 2 ms 10844 KB ok
29 Correct 3 ms 12636 KB ok
30 Correct 2 ms 10588 KB ok
31 Correct 2 ms 10840 KB ok
32 Correct 2 ms 10588 KB ok
33 Correct 2 ms 12636 KB ok
34 Correct 2 ms 12636 KB ok
35 Correct 2 ms 12636 KB ok
36 Correct 2 ms 12636 KB ok
37 Correct 2 ms 12644 KB ok
38 Correct 2 ms 12896 KB ok
39 Correct 2 ms 12640 KB ok
40 Correct 2 ms 10596 KB ok
41 Correct 2 ms 10592 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 2 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 2 ms 10588 KB ok
8 Correct 2 ms 10584 KB ok
9 Correct 2 ms 12632 KB ok
10 Correct 2 ms 10720 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 2 ms 10740 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 2 ms 12632 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 2 ms 10588 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 2 ms 10588 KB ok
22 Correct 2 ms 12716 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12636 KB ok
25 Correct 2 ms 12632 KB ok
26 Correct 2 ms 12632 KB ok
27 Correct 2 ms 12636 KB ok
28 Correct 2 ms 10844 KB ok
29 Correct 3 ms 12636 KB ok
30 Correct 2 ms 10588 KB ok
31 Correct 2 ms 10840 KB ok
32 Correct 2 ms 10588 KB ok
33 Correct 2 ms 12636 KB ok
34 Correct 2 ms 12636 KB ok
35 Correct 2 ms 12636 KB ok
36 Correct 2 ms 12636 KB ok
37 Correct 2 ms 12644 KB ok
38 Correct 2 ms 12896 KB ok
39 Correct 2 ms 12640 KB ok
40 Correct 2 ms 10596 KB ok
41 Correct 2 ms 10592 KB ok
42 Correct 73 ms 34060 KB ok
43 Correct 55 ms 31276 KB ok
44 Correct 63 ms 36076 KB ok
45 Correct 66 ms 36300 KB ok
46 Correct 63 ms 35552 KB ok
47 Correct 48 ms 37432 KB ok
48 Correct 37 ms 28300 KB ok
49 Correct 35 ms 28504 KB ok
50 Correct 41 ms 32732 KB ok
51 Correct 47 ms 37072 KB ok
52 Correct 24 ms 20564 KB ok
53 Correct 23 ms 19548 KB ok
54 Correct 25 ms 20364 KB ok
55 Correct 32 ms 21148 KB ok
56 Correct 29 ms 22628 KB ok
57 Correct 55 ms 37060 KB ok
58 Correct 49 ms 37280 KB ok
59 Correct 48 ms 37604 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 2 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 2 ms 10744 KB ok
7 Correct 2 ms 10588 KB ok
8 Correct 4 ms 13404 KB ok
9 Correct 54 ms 37644 KB ok
10 Correct 785 ms 387640 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 2 ms 10584 KB ok
14 Correct 2 ms 12632 KB ok
15 Correct 2 ms 10720 KB ok
16 Correct 2 ms 10584 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 2 ms 10740 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 2 ms 12632 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 2 ms 10588 KB ok
25 Correct 1 ms 10588 KB ok
26 Correct 2 ms 10588 KB ok
27 Correct 2 ms 12716 KB ok
28 Correct 2 ms 12636 KB ok
29 Correct 2 ms 12636 KB ok
30 Correct 2 ms 12632 KB ok
31 Correct 2 ms 12632 KB ok
32 Correct 2 ms 12636 KB ok
33 Correct 2 ms 10844 KB ok
34 Correct 3 ms 12636 KB ok
35 Correct 2 ms 10588 KB ok
36 Correct 2 ms 10840 KB ok
37 Correct 2 ms 10588 KB ok
38 Correct 2 ms 12636 KB ok
39 Correct 2 ms 12636 KB ok
40 Correct 2 ms 12636 KB ok
41 Correct 2 ms 12636 KB ok
42 Correct 2 ms 12644 KB ok
43 Correct 2 ms 12896 KB ok
44 Correct 2 ms 12640 KB ok
45 Correct 2 ms 10596 KB ok
46 Correct 2 ms 10592 KB ok
47 Correct 73 ms 34060 KB ok
48 Correct 55 ms 31276 KB ok
49 Correct 63 ms 36076 KB ok
50 Correct 66 ms 36300 KB ok
51 Correct 63 ms 35552 KB ok
52 Correct 48 ms 37432 KB ok
53 Correct 37 ms 28300 KB ok
54 Correct 35 ms 28504 KB ok
55 Correct 41 ms 32732 KB ok
56 Correct 47 ms 37072 KB ok
57 Correct 24 ms 20564 KB ok
58 Correct 23 ms 19548 KB ok
59 Correct 25 ms 20364 KB ok
60 Correct 32 ms 21148 KB ok
61 Correct 29 ms 22628 KB ok
62 Correct 55 ms 37060 KB ok
63 Correct 49 ms 37280 KB ok
64 Correct 48 ms 37604 KB ok
65 Correct 1445 ms 349116 KB ok
66 Correct 574 ms 155180 KB ok
67 Correct 399 ms 82352 KB ok
68 Correct 1656 ms 394484 KB ok
69 Correct 2102 ms 382136 KB ok
70 Correct 1927 ms 377388 KB ok
71 Correct 1346 ms 395612 KB ok
72 Correct 651 ms 385660 KB ok
73 Correct 749 ms 230152 KB ok
74 Correct 732 ms 236432 KB ok
75 Correct 725 ms 233760 KB ok
76 Correct 572 ms 299676 KB ok
77 Correct 556 ms 299748 KB ok
78 Correct 960 ms 377636 KB ok
79 Correct 366 ms 66968 KB ok
80 Correct 356 ms 67492 KB ok
81 Correct 477 ms 87604 KB ok
82 Correct 629 ms 138452 KB ok
83 Correct 505 ms 117460 KB ok
84 Correct 418 ms 81188 KB ok
85 Correct 358 ms 70044 KB ok
86 Correct 420 ms 100396 KB ok
87 Correct 419 ms 101932 KB ok
88 Correct 501 ms 194592 KB ok
89 Correct 615 ms 382120 KB ok
90 Correct 566 ms 307412 KB ok
91 Correct 668 ms 357120 KB ok
92 Correct 427 ms 89740 KB ok
93 Correct 406 ms 84892 KB ok
94 Correct 375 ms 74384 KB ok
95 Correct 388 ms 79260 KB ok
96 Correct 374 ms 79252 KB ok
97 Correct 343 ms 78216 KB ok
98 Correct 333 ms 62396 KB ok
99 Correct 879 ms 364760 KB ok
100 Correct 983 ms 410496 KB ok
101 Correct 1071 ms 411732 KB ok
102 Correct 1105 ms 410168 KB ok
103 Correct 1031 ms 411928 KB ok
104 Correct 1097 ms 409900 KB ok
105 Correct 1087 ms 409984 KB ok
106 Correct 1048 ms 415684 KB ok
107 Correct 1117 ms 418012 KB ok
108 Correct 703 ms 332300 KB ok
109 Correct 721 ms 332304 KB ok