oj.uz

Submission #1076909

# Submission time Handle Problem Language Result Execution time Memory
1076909 2024-08-26T18:52:07 Z mickey080929 Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 655 ms 512892 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int dp[510][510][510];
vector<pair<int,int>> ran[510][510];

int large_case(int N, vector<vector<int>> F) {
    vector<vector<int>> vis(N, vector<int>(N, 0));
    queue<pair<int,int>> q;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (F[i][j] == 0) {
                vis[i][j] = 1;
                q.push({i, j});
                break;
            }
        }
        if (!q.empty()) break;
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k=0; k<4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (vis[nx][ny]) continue;
            if (F[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (F[i][j] == 0 && vis[i][j] == 0) {
                return 0;
            }
        }
    }
    int tot = 0;
    bool flag = false;
    int pl = -1, pr = -1;
    vector<pair<int,int>> ran;
    for (int i=0; i<N; i++) {
        int l = -1, r = -1, cnt = 0;
        for (int j=0; j<N; j++) {
            if (F[i][j] == 0) {
                if (l == -1) l = j;
                r = j;
                cnt ++;
            }
        }
        if (cnt == 0) {
            pl = -1; pr = -1;
            continue;
        }
        ran.push_back({l, r});
        if (r - l + 1 != cnt) {
            return 0;
        }
        if (pl != -1) {
            if (!flag) {
                if (l <= pl && pr <= r) {}
                else if (pl <= l && r <= pr) {
                    flag = true;
                }
                else return 0;
            }
            else {
                if (pl <= l && r <= pr) {}
                else return 0;
            }
        }
        pl = l; pr = r;
        tot += cnt;
    }
    sort(ran.begin(), ran.end(), [&](pair<int,int> &u, pair<int,int> &v) {
        return u.second - u.first < v.second - v.first;
    });
    for (int i=0; i+1<ran.size(); i++) {
        if (ran[i+1].first <= ran[i].first && ran[i].second <= ran[i+1].second) {}
        else return 0;
    }
    return tot;
}

int biggest_stadium(int N, vector<vector<int>> F) {
    int tot = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (F[i][j] == 1) {
                tot ++;
            }
        }
    }
    if (tot == 0) return N * N;
    if (tot == 1) {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (F[i][j] == 1) {
                    return N * N - min(i+1, N-i) * min(j+1, N-j);
                }
            }
        }
    }
    if (N > 500) {
        return large_case(N, F);
    }
    for (int i=0; i<N; i++) {
        vector<int> cnt(N, 0);
        for (int j=i; j<N; j++) {
            for (int k=0; k<N; k++) {
                if (F[j][k] == 0) {
                    cnt[k] ++;
                }
            }
            int l = -1;
            for (int k=0; k<N; k++) {
                if (cnt[k] == j-i+1) {
                    if (l == -1) l = k;
                    if (k == N-1 || cnt[k+1] != j-i+1) {
                        ran[i][j].push_back({l, k});
                    }
                }
                else l = -1;
            }
        }
    }
    int ans = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<ran[i][i].size(); j++) {
            dp[i][i][j] = ran[i][i][j].second - ran[i][i][j].first + 1;
            ans = max(ans, dp[i][i][j]);
        }
    }
    for (int d=1; d<=N-1; d++) {
        for (int i=0; i<N-d; i++) {
            int j = i + d;
            int l = 0;
            for (int k=0; k<ran[i][j].size(); k++) {
                while (ran[i][j-1][l].second < ran[i][j][k].first)
                    l ++;
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][l] + ran[i][j][k].second - ran[i][j][k].first + 1);
                ans = max(ans, dp[i][j][k]);
            }
            l = 0;
            for (int k=0; k<ran[i][j].size(); k++) {
                while (ran[i+1][j][l].second < ran[i][j][k].first)
                    l ++;
                dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][l] + ran[i][j][k].second - ran[i][j][k].first + 1);
                ans = max(ans, dp[i][j][k]);
            }
        }
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'int large_case(int, std::vector<std::vector<int> >)':
soccer.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=0; i+1<ran.size(); i++) {
      |                   ~~~^~~~~~~~~~~
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int j=0; j<ran[i][i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~~~
soccer.cpp:146:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~
soccer.cpp:153:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 2 ms 6492 KB ok
3 Correct 3 ms 6492 KB ok
4 Correct 2 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6492 KB ok
7 Correct 3 ms 6500 KB ok
8 Correct 15 ms 8540 KB ok
9 Correct 198 ms 37880 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 2 ms 6492 KB ok
3 Correct 5 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 3 ms 6516 KB ok
6 Correct 3 ms 6488 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6492 KB ok
9 Correct 2 ms 6492 KB ok
10 Correct 3 ms 6492 KB ok
11 Correct 2 ms 6492 KB ok
12 Correct 3 ms 6488 KB ok
13 Correct 5 ms 6492 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 2 ms 6492 KB ok
4 Correct 5 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6516 KB ok
7 Correct 3 ms 6488 KB ok
8 Correct 3 ms 6492 KB ok
9 Correct 3 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 3 ms 6492 KB ok
12 Correct 2 ms 6492 KB ok
13 Correct 3 ms 6488 KB ok
14 Correct 5 ms 6492 KB ok
15 Correct 3 ms 6492 KB ok
16 Correct 3 ms 6492 KB ok
17 Correct 3 ms 6492 KB ok
18 Correct 3 ms 6492 KB ok
19 Correct 3 ms 6492 KB ok
20 Correct 3 ms 6492 KB ok
21 Correct 3 ms 6476 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 3 ms 6488 KB ok
24 Correct 3 ms 6492 KB ok
25 Correct 3 ms 6492 KB ok
26 Correct 2 ms 6492 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 2 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 2 ms 6492 KB ok
6 Correct 5 ms 6492 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6516 KB ok
9 Correct 3 ms 6488 KB ok
10 Correct 3 ms 6492 KB ok
11 Correct 3 ms 6492 KB ok
12 Correct 2 ms 6492 KB ok
13 Correct 3 ms 6492 KB ok
14 Correct 2 ms 6492 KB ok
15 Correct 3 ms 6488 KB ok
16 Correct 5 ms 6492 KB ok
17 Correct 3 ms 6492 KB ok
18 Correct 3 ms 6492 KB ok
19 Correct 3 ms 6492 KB ok
20 Correct 3 ms 6492 KB ok
21 Correct 3 ms 6492 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 3 ms 6476 KB ok
24 Correct 3 ms 6492 KB ok
25 Correct 3 ms 6488 KB ok
26 Correct 3 ms 6492 KB ok
27 Correct 3 ms 6492 KB ok
28 Correct 2 ms 6492 KB ok
29 Correct 3 ms 6492 KB ok
30 Correct 3 ms 7516 KB ok
31 Correct 3 ms 7260 KB ok
32 Correct 3 ms 6748 KB ok
33 Correct 3 ms 6492 KB ok
34 Correct 5 ms 7516 KB ok
35 Correct 3 ms 6984 KB ok
36 Correct 3 ms 6748 KB ok
37 Correct 3 ms 6748 KB ok
38 Correct 3 ms 6748 KB ok
39 Correct 3 ms 7032 KB ok
40 Correct 4 ms 7004 KB ok
41 Correct 3 ms 7516 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 2 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 2 ms 6492 KB ok
6 Correct 5 ms 6492 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6516 KB ok
9 Correct 3 ms 6488 KB ok
10 Correct 3 ms 6492 KB ok
11 Correct 3 ms 6492 KB ok
12 Correct 2 ms 6492 KB ok
13 Correct 3 ms 6492 KB ok
14 Correct 2 ms 6492 KB ok
15 Correct 3 ms 6488 KB ok
16 Correct 5 ms 6492 KB ok
17 Correct 3 ms 6492 KB ok
18 Correct 3 ms 6492 KB ok
19 Correct 3 ms 6492 KB ok
20 Correct 3 ms 6492 KB ok
21 Correct 3 ms 6492 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 3 ms 6476 KB ok
24 Correct 3 ms 6492 KB ok
25 Correct 3 ms 6488 KB ok
26 Correct 3 ms 6492 KB ok
27 Correct 3 ms 6492 KB ok
28 Correct 2 ms 6492 KB ok
29 Correct 3 ms 6492 KB ok
30 Correct 3 ms 7516 KB ok
31 Correct 3 ms 7260 KB ok
32 Correct 3 ms 6748 KB ok
33 Correct 3 ms 6492 KB ok
34 Correct 5 ms 7516 KB ok
35 Correct 3 ms 6984 KB ok
36 Correct 3 ms 6748 KB ok
37 Correct 3 ms 6748 KB ok
38 Correct 3 ms 6748 KB ok
39 Correct 3 ms 7032 KB ok
40 Correct 4 ms 7004 KB ok
41 Correct 3 ms 7516 KB ok
42 Correct 202 ms 80276 KB ok
43 Correct 209 ms 45392 KB ok
44 Correct 377 ms 350032 KB ok
45 Correct 414 ms 377452 KB ok
46 Correct 235 ms 164472 KB ok
47 Correct 258 ms 269904 KB ok
48 Correct 242 ms 257872 KB ok
49 Correct 242 ms 238064 KB ok
50 Correct 655 ms 512892 KB ok
51 Correct 189 ms 138580 KB ok
52 Correct 148 ms 89208 KB ok
53 Correct 114 ms 29528 KB ok
54 Correct 154 ms 99156 KB ok
55 Correct 226 ms 215636 KB ok
56 Correct 150 ms 70744 KB ok
57 Correct 243 ms 263832 KB ok
58 Correct 245 ms 262228 KB ok
59 Correct 244 ms 253520 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 2 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 2 ms 6492 KB ok
6 Correct 3 ms 6492 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6500 KB ok
9 Correct 15 ms 8540 KB ok
10 Correct 198 ms 37880 KB ok
11 Correct 5 ms 6492 KB ok
12 Correct 3 ms 6492 KB ok
13 Correct 3 ms 6516 KB ok
14 Correct 3 ms 6488 KB ok
15 Correct 3 ms 6492 KB ok
16 Correct 3 ms 6492 KB ok
17 Correct 2 ms 6492 KB ok
18 Correct 3 ms 6492 KB ok
19 Correct 2 ms 6492 KB ok
20 Correct 3 ms 6488 KB ok
21 Correct 5 ms 6492 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 3 ms 6492 KB ok
24 Correct 3 ms 6492 KB ok
25 Correct 3 ms 6492 KB ok
26 Correct 3 ms 6492 KB ok
27 Correct 3 ms 6492 KB ok
28 Correct 3 ms 6476 KB ok
29 Correct 3 ms 6492 KB ok
30 Correct 3 ms 6488 KB ok
31 Correct 3 ms 6492 KB ok
32 Correct 3 ms 6492 KB ok
33 Correct 2 ms 6492 KB ok
34 Correct 3 ms 6492 KB ok
35 Correct 3 ms 7516 KB ok
36 Correct 3 ms 7260 KB ok
37 Correct 3 ms 6748 KB ok
38 Correct 3 ms 6492 KB ok
39 Correct 5 ms 7516 KB ok
40 Correct 3 ms 6984 KB ok
41 Correct 3 ms 6748 KB ok
42 Correct 3 ms 6748 KB ok
43 Correct 3 ms 6748 KB ok
44 Correct 3 ms 7032 KB ok
45 Correct 4 ms 7004 KB ok
46 Correct 3 ms 7516 KB ok
47 Correct 202 ms 80276 KB ok
48 Correct 209 ms 45392 KB ok
49 Correct 377 ms 350032 KB ok
50 Correct 414 ms 377452 KB ok
51 Correct 235 ms 164472 KB ok
52 Correct 258 ms 269904 KB ok
53 Correct 242 ms 257872 KB ok
54 Correct 242 ms 238064 KB ok
55 Correct 655 ms 512892 KB ok
56 Correct 189 ms 138580 KB ok
57 Correct 148 ms 89208 KB ok
58 Correct 114 ms 29528 KB ok
59 Correct 154 ms 99156 KB ok
60 Correct 226 ms 215636 KB ok
61 Correct 150 ms 70744 KB ok
62 Correct 243 ms 263832 KB ok
63 Correct 245 ms 262228 KB ok
64 Correct 244 ms 253520 KB ok
65 Partially correct 295 ms 69372 KB partial
66 Partially correct 236 ms 77140 KB partial
67 Partially correct 228 ms 77140 KB partial
68 Partially correct 282 ms 74580 KB partial
69 Partially correct 290 ms 77140 KB partial
70 Partially correct 277 ms 77140 KB partial
71 Partially correct 276 ms 77136 KB partial
72 Partially correct 286 ms 77140 KB partial
73 Correct 264 ms 77140 KB ok
74 Correct 281 ms 77144 KB ok
75 Partially correct 279 ms 77140 KB partial
76 Partially correct 292 ms 77140 KB partial
77 Partially correct 290 ms 76884 KB partial
78 Partially correct 221 ms 77136 KB partial
79 Partially correct 221 ms 77136 KB partial
80 Partially correct 233 ms 77140 KB partial
81 Partially correct 221 ms 77180 KB partial
82 Partially correct 213 ms 77136 KB partial
83 Partially correct 222 ms 77140 KB partial
84 Partially correct 223 ms 77164 KB partial
85 Partially correct 236 ms 77180 KB partial
86 Partially correct 241 ms 77292 KB partial
87 Partially correct 257 ms 77136 KB partial
88 Partially correct 252 ms 77164 KB partial
89 Partially correct 277 ms 76116 KB partial
90 Partially correct 310 ms 77036 KB partial
91 Partially correct 290 ms 77036 KB partial
92 Partially correct 221 ms 77168 KB partial
93 Partially correct 218 ms 77032 KB partial
94 Partially correct 222 ms 77136 KB partial
95 Partially correct 229 ms 77140 KB partial
96 Partially correct 213 ms 77136 KB partial
97 Partially correct 219 ms 77136 KB partial
98 Partially correct 211 ms 77136 KB partial
99 Partially correct 215 ms 77136 KB partial
100 Partially correct 273 ms 77048 KB partial
101 Partially correct 224 ms 77136 KB partial
102 Partially correct 228 ms 77140 KB partial
103 Partially correct 245 ms 77136 KB partial
104 Partially correct 237 ms 77032 KB partial
105 Partially correct 224 ms 77140 KB partial
106 Partially correct 240 ms 77036 KB partial
107 Partially correct 243 ms 77140 KB partial
108 Partially correct 225 ms 77160 KB partial
109 Partially correct 220 ms 77136 KB partial