oj.uz

Submission #964430

# Submission time Handle Problem Language Result Execution time Memory
964430 2024-04-16T19:56:30 Z nguyentunglam Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 668452 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];

vector<tuple<int, int, int, int> > rect;

int solve() {

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

  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.emplace_back(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.emplace_back(i, i + b[j] - 1, L[j] + 1, R[j] - 1);
    }
  }

  sort(all(rect));
  rect.resize(unique(all(rect)) - rect.begin());

  auto idx = [&] (int x1, int x2, int y1, int y2) {
    return upper_bound(all(rect), make_tuple(x1, x2, y1, y2)) - rect.begin();
  };

  vector<tuple<int, int, int, int> > _rect = rect;
  sort(all(_rect), [&] (const tuple<int, int, int, int> &x, const tuple<int, int, int, int> &y) {
    return get<1> (x) - get<0> (x) < get<1> (y) - get<0> (y);
  });

  for(auto &[x1, x2, y1, y2] : _rect) {
    int i = idx(x1, x2, y1, y2);
//    cout << x1 << " " << x2 << " " << y1 << " " << y2 << endl;
    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(auto &[x1, x2, y1, y2] : rect) {
    int i = idx(x1, x2, y1, y2);
//    cout << x1 << " " << x2 << " " << y1 << " " << y2 << endl;
//    cout << trans[0][i] << " " << trans[1][i] << " " << i << endl;
  }

//  exit(0);


  for(auto &[x1, x2, y1, y2] : _rect) {
    int i = idx(x1, x2, y1, y2);
//    cout << trans[0][i] << " " << trans[1][i] << endl;
    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 - 1]) - x1) * (y2 - y1 + 1));
    }
    if (trans[1][i]) {
      int j = trans[1][i];
      dp[i] = max(dp[i], dp[j] + (x2 - get<1> (rect[j - 1])) * (y2 - y1 + 1));
    }
    ans = max(ans, dp[i]);
  }

  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;
      |                                     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp: In function 'int AC::solve()':
soccer.cpp:187:9: warning: unused variable 'i' [-Wunused-variable]
  187 |     int i = idx(x1, x2, y1, y2);
      |         ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 201576 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 201560 KB ok
2 Correct 46 ms 201556 KB ok
3 Correct 51 ms 203560 KB ok
4 Correct 46 ms 201556 KB ok
5 Correct 48 ms 201556 KB ok
6 Correct 45 ms 201552 KB ok
7 Correct 47 ms 202200 KB ok
8 Correct 94 ms 222340 KB ok
9 Correct 816 ms 396320 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 201560 KB ok
2 Correct 46 ms 201556 KB ok
3 Correct 45 ms 201668 KB ok
4 Correct 46 ms 201564 KB ok
5 Correct 45 ms 201664 KB ok
6 Correct 45 ms 203612 KB ok
7 Correct 45 ms 201556 KB ok
8 Correct 45 ms 201552 KB ok
9 Correct 47 ms 201552 KB ok
10 Correct 44 ms 201564 KB ok
11 Correct 46 ms 201556 KB ok
12 Correct 45 ms 201556 KB ok
13 Correct 48 ms 203612 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 201576 KB ok
2 Correct 46 ms 201560 KB ok
3 Correct 46 ms 201556 KB ok
4 Correct 45 ms 201668 KB ok
5 Correct 46 ms 201564 KB ok
6 Correct 45 ms 201664 KB ok
7 Correct 45 ms 203612 KB ok
8 Correct 45 ms 201556 KB ok
9 Correct 45 ms 201552 KB ok
10 Correct 47 ms 201552 KB ok
11 Correct 44 ms 201564 KB ok
12 Correct 46 ms 201556 KB ok
13 Correct 45 ms 201556 KB ok
14 Correct 48 ms 203612 KB ok
15 Correct 46 ms 201692 KB ok
16 Correct 48 ms 201556 KB ok
17 Correct 47 ms 201556 KB ok
18 Correct 45 ms 201556 KB ok
19 Correct 47 ms 202068 KB ok
20 Correct 49 ms 203600 KB ok
21 Correct 46 ms 203712 KB ok
22 Correct 46 ms 203688 KB ok
23 Correct 45 ms 203728 KB ok
24 Correct 46 ms 203548 KB ok
25 Correct 48 ms 203600 KB ok
26 Correct 45 ms 201556 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 201576 KB ok
2 Correct 46 ms 201560 KB ok
3 Correct 46 ms 201556 KB ok
4 Correct 51 ms 203560 KB ok
5 Correct 46 ms 201556 KB ok
6 Correct 45 ms 201668 KB ok
7 Correct 46 ms 201564 KB ok
8 Correct 45 ms 201664 KB ok
9 Correct 45 ms 203612 KB ok
10 Correct 45 ms 201556 KB ok
11 Correct 45 ms 201552 KB ok
12 Correct 47 ms 201552 KB ok
13 Correct 44 ms 201564 KB ok
14 Correct 46 ms 201556 KB ok
15 Correct 45 ms 201556 KB ok
16 Correct 48 ms 203612 KB ok
17 Correct 46 ms 201692 KB ok
18 Correct 48 ms 201556 KB ok
19 Correct 47 ms 201556 KB ok
20 Correct 45 ms 201556 KB ok
21 Correct 47 ms 202068 KB ok
22 Correct 49 ms 203600 KB ok
23 Correct 46 ms 203712 KB ok
24 Correct 46 ms 203688 KB ok
25 Correct 45 ms 203728 KB ok
26 Correct 46 ms 203548 KB ok
27 Correct 48 ms 203600 KB ok
28 Correct 45 ms 201556 KB ok
29 Correct 45 ms 203612 KB ok
30 Correct 47 ms 201776 KB ok
31 Correct 46 ms 201552 KB ok
32 Correct 46 ms 201564 KB ok
33 Correct 45 ms 203648 KB ok
34 Correct 45 ms 203668 KB ok
35 Correct 46 ms 203964 KB ok
36 Correct 46 ms 203880 KB ok
37 Correct 49 ms 203744 KB ok
38 Correct 51 ms 203608 KB ok
39 Correct 46 ms 203684 KB ok
40 Correct 45 ms 201776 KB ok
41 Correct 48 ms 201664 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 201576 KB ok
2 Correct 46 ms 201560 KB ok
3 Correct 46 ms 201556 KB ok
4 Correct 51 ms 203560 KB ok
5 Correct 46 ms 201556 KB ok
6 Correct 45 ms 201668 KB ok
7 Correct 46 ms 201564 KB ok
8 Correct 45 ms 201664 KB ok
9 Correct 45 ms 203612 KB ok
10 Correct 45 ms 201556 KB ok
11 Correct 45 ms 201552 KB ok
12 Correct 47 ms 201552 KB ok
13 Correct 44 ms 201564 KB ok
14 Correct 46 ms 201556 KB ok
15 Correct 45 ms 201556 KB ok
16 Correct 48 ms 203612 KB ok
17 Correct 46 ms 201692 KB ok
18 Correct 48 ms 201556 KB ok
19 Correct 47 ms 201556 KB ok
20 Correct 45 ms 201556 KB ok
21 Correct 47 ms 202068 KB ok
22 Correct 49 ms 203600 KB ok
23 Correct 46 ms 203712 KB ok
24 Correct 46 ms 203688 KB ok
25 Correct 45 ms 203728 KB ok
26 Correct 46 ms 203548 KB ok
27 Correct 48 ms 203600 KB ok
28 Correct 45 ms 201556 KB ok
29 Correct 45 ms 203612 KB ok
30 Correct 47 ms 201776 KB ok
31 Correct 46 ms 201552 KB ok
32 Correct 46 ms 201564 KB ok
33 Correct 45 ms 203648 KB ok
34 Correct 45 ms 203668 KB ok
35 Correct 46 ms 203964 KB ok
36 Correct 46 ms 203880 KB ok
37 Correct 49 ms 203744 KB ok
38 Correct 51 ms 203608 KB ok
39 Correct 46 ms 203684 KB ok
40 Correct 45 ms 201776 KB ok
41 Correct 48 ms 201664 KB ok
42 Correct 287 ms 237284 KB ok
43 Correct 240 ms 235560 KB ok
44 Correct 351 ms 242092 KB ok
45 Correct 314 ms 240808 KB ok
46 Correct 327 ms 241580 KB ok
47 Correct 105 ms 222892 KB ok
48 Correct 123 ms 224436 KB ok
49 Correct 118 ms 225712 KB ok
50 Correct 156 ms 237740 KB ok
51 Correct 186 ms 233924 KB ok
52 Correct 87 ms 219072 KB ok
53 Correct 72 ms 216564 KB ok
54 Correct 81 ms 215296 KB ok
55 Correct 98 ms 218660 KB ok
56 Correct 95 ms 214716 KB ok
57 Correct 185 ms 232448 KB ok
58 Correct 198 ms 233096 KB ok
59 Correct 205 ms 233824 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 201576 KB ok
2 Correct 46 ms 201560 KB ok
3 Correct 46 ms 201556 KB ok
4 Correct 51 ms 203560 KB ok
5 Correct 46 ms 201556 KB ok
6 Correct 48 ms 201556 KB ok
7 Correct 45 ms 201552 KB ok
8 Correct 47 ms 202200 KB ok
9 Correct 94 ms 222340 KB ok
10 Correct 816 ms 396320 KB ok
11 Correct 45 ms 201668 KB ok
12 Correct 46 ms 201564 KB ok
13 Correct 45 ms 201664 KB ok
14 Correct 45 ms 203612 KB ok
15 Correct 45 ms 201556 KB ok
16 Correct 45 ms 201552 KB ok
17 Correct 47 ms 201552 KB ok
18 Correct 44 ms 201564 KB ok
19 Correct 46 ms 201556 KB ok
20 Correct 45 ms 201556 KB ok
21 Correct 48 ms 203612 KB ok
22 Correct 46 ms 201692 KB ok
23 Correct 48 ms 201556 KB ok
24 Correct 47 ms 201556 KB ok
25 Correct 45 ms 201556 KB ok
26 Correct 47 ms 202068 KB ok
27 Correct 49 ms 203600 KB ok
28 Correct 46 ms 203712 KB ok
29 Correct 46 ms 203688 KB ok
30 Correct 45 ms 203728 KB ok
31 Correct 46 ms 203548 KB ok
32 Correct 48 ms 203600 KB ok
33 Correct 45 ms 201556 KB ok
34 Correct 45 ms 203612 KB ok
35 Correct 47 ms 201776 KB ok
36 Correct 46 ms 201552 KB ok
37 Correct 46 ms 201564 KB ok
38 Correct 45 ms 203648 KB ok
39 Correct 45 ms 203668 KB ok
40 Correct 46 ms 203964 KB ok
41 Correct 46 ms 203880 KB ok
42 Correct 49 ms 203744 KB ok
43 Correct 51 ms 203608 KB ok
44 Correct 46 ms 203684 KB ok
45 Correct 45 ms 201776 KB ok
46 Correct 48 ms 201664 KB ok
47 Correct 287 ms 237284 KB ok
48 Correct 240 ms 235560 KB ok
49 Correct 351 ms 242092 KB ok
50 Correct 314 ms 240808 KB ok
51 Correct 327 ms 241580 KB ok
52 Correct 105 ms 222892 KB ok
53 Correct 123 ms 224436 KB ok
54 Correct 118 ms 225712 KB ok
55 Correct 156 ms 237740 KB ok
56 Correct 186 ms 233924 KB ok
57 Correct 87 ms 219072 KB ok
58 Correct 72 ms 216564 KB ok
59 Correct 81 ms 215296 KB ok
60 Correct 98 ms 218660 KB ok
61 Correct 95 ms 214716 KB ok
62 Correct 185 ms 232448 KB ok
63 Correct 198 ms 233096 KB ok
64 Correct 205 ms 233824 KB ok
65 Execution timed out 4532 ms 668452 KB Time limit exceeded
66 Halted 0 ms 0 KB -