oj.uz

Submission #1076908

# Submission time Handle Problem Language Result Execution time Memory
1076908 2024-08-26T18:51:19 Z mickey080929 Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 513584 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 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);
                }
            }
        }
    }
    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 biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:53: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]
   53 |         for (int j=0; j<ran[i][i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~~~
soccer.cpp:62: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]
   62 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~
soccer.cpp:69: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]
   69 |             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 6492 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6504 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 3 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6492 KB ok
7 Correct 4 ms 6492 KB ok
8 Correct 16 ms 8816 KB ok
9 Correct 209 ms 45136 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 3 ms 6504 KB ok
3 Correct 3 ms 6492 KB ok
4 Correct 3 ms 6556 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6492 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6492 KB ok
9 Correct 3 ms 6492 KB ok
10 Correct 3 ms 6488 KB ok
11 Correct 3 ms 6488 KB ok
12 Correct 3 ms 6492 KB ok
13 Correct 3 ms 6492 KB ok
14 Correct 3 ms 6492 KB ok
15 Correct 3 ms 6488 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 2 ms 6492 KB ok
20 Correct 3 ms 6492 KB ok
21 Correct 3 ms 6492 KB ok
22 Correct 3 ms 6488 KB ok
23 Correct 3 ms 6492 KB ok
24 Correct 2 ms 6492 KB ok
25 Correct 3 ms 6492 KB ok
26 Correct 3 ms 6612 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 3 ms 6504 KB ok
3 Correct 3 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6556 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6492 KB ok
9 Correct 3 ms 6492 KB ok
10 Correct 3 ms 6492 KB ok
11 Correct 3 ms 6492 KB ok
12 Correct 3 ms 6488 KB ok
13 Correct 3 ms 6488 KB ok
14 Correct 3 ms 6492 KB ok
15 Correct 3 ms 6492 KB ok
16 Correct 3 ms 6492 KB ok
17 Correct 3 ms 6488 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 2 ms 6492 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 3 ms 6492 KB ok
24 Correct 3 ms 6488 KB ok
25 Correct 3 ms 6492 KB ok
26 Correct 2 ms 6492 KB ok
27 Correct 3 ms 6492 KB ok
28 Correct 3 ms 6612 KB ok
29 Correct 3 ms 6488 KB ok
30 Correct 3 ms 7576 KB ok
31 Correct 4 ms 7308 KB ok
32 Correct 3 ms 6748 KB ok
33 Correct 3 ms 6492 KB ok
34 Correct 4 ms 7516 KB ok
35 Correct 3 ms 7004 KB ok
36 Correct 3 ms 6748 KB ok
37 Correct 3 ms 6748 KB ok
38 Correct 4 ms 6744 KB ok
39 Correct 3 ms 7004 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 6492 KB ok
2 Correct 3 ms 6504 KB ok
3 Correct 3 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6556 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 3 ms 6492 KB ok
9 Correct 3 ms 6492 KB ok
10 Correct 3 ms 6492 KB ok
11 Correct 3 ms 6492 KB ok
12 Correct 3 ms 6488 KB ok
13 Correct 3 ms 6488 KB ok
14 Correct 3 ms 6492 KB ok
15 Correct 3 ms 6492 KB ok
16 Correct 3 ms 6492 KB ok
17 Correct 3 ms 6488 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 2 ms 6492 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 3 ms 6492 KB ok
24 Correct 3 ms 6488 KB ok
25 Correct 3 ms 6492 KB ok
26 Correct 2 ms 6492 KB ok
27 Correct 3 ms 6492 KB ok
28 Correct 3 ms 6612 KB ok
29 Correct 3 ms 6488 KB ok
30 Correct 3 ms 7576 KB ok
31 Correct 4 ms 7308 KB ok
32 Correct 3 ms 6748 KB ok
33 Correct 3 ms 6492 KB ok
34 Correct 4 ms 7516 KB ok
35 Correct 3 ms 7004 KB ok
36 Correct 3 ms 6748 KB ok
37 Correct 3 ms 6748 KB ok
38 Correct 4 ms 6744 KB ok
39 Correct 3 ms 7004 KB ok
40 Correct 4 ms 7004 KB ok
41 Correct 3 ms 7516 KB ok
42 Correct 203 ms 80544 KB ok
43 Correct 211 ms 45908 KB ok
44 Correct 357 ms 350800 KB ok
45 Correct 397 ms 377940 KB ok
46 Correct 230 ms 164944 KB ok
47 Correct 257 ms 270356 KB ok
48 Correct 258 ms 258388 KB ok
49 Correct 232 ms 238676 KB ok
50 Correct 656 ms 513584 KB ok
51 Correct 193 ms 139092 KB ok
52 Correct 154 ms 89572 KB ok
53 Correct 121 ms 30036 KB ok
54 Correct 157 ms 99676 KB ok
55 Correct 234 ms 216144 KB ok
56 Correct 140 ms 71248 KB ok
57 Correct 243 ms 264268 KB ok
58 Correct 248 ms 262736 KB ok
59 Correct 230 ms 253916 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 3 ms 6504 KB ok
3 Correct 3 ms 6492 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6492 KB ok
7 Correct 3 ms 6492 KB ok
8 Correct 4 ms 6492 KB ok
9 Correct 16 ms 8816 KB ok
10 Correct 209 ms 45136 KB ok
11 Correct 3 ms 6556 KB ok
12 Correct 3 ms 6492 KB ok
13 Correct 3 ms 6492 KB ok
14 Correct 3 ms 6492 KB ok
15 Correct 3 ms 6492 KB ok
16 Correct 3 ms 6492 KB ok
17 Correct 3 ms 6488 KB ok
18 Correct 3 ms 6488 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 6488 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 2 ms 6492 KB ok
27 Correct 3 ms 6492 KB ok
28 Correct 3 ms 6492 KB ok
29 Correct 3 ms 6488 KB ok
30 Correct 3 ms 6492 KB ok
31 Correct 2 ms 6492 KB ok
32 Correct 3 ms 6492 KB ok
33 Correct 3 ms 6612 KB ok
34 Correct 3 ms 6488 KB ok
35 Correct 3 ms 7576 KB ok
36 Correct 4 ms 7308 KB ok
37 Correct 3 ms 6748 KB ok
38 Correct 3 ms 6492 KB ok
39 Correct 4 ms 7516 KB ok
40 Correct 3 ms 7004 KB ok
41 Correct 3 ms 6748 KB ok
42 Correct 3 ms 6748 KB ok
43 Correct 4 ms 6744 KB ok
44 Correct 3 ms 7004 KB ok
45 Correct 4 ms 7004 KB ok
46 Correct 3 ms 7516 KB ok
47 Correct 203 ms 80544 KB ok
48 Correct 211 ms 45908 KB ok
49 Correct 357 ms 350800 KB ok
50 Correct 397 ms 377940 KB ok
51 Correct 230 ms 164944 KB ok
52 Correct 257 ms 270356 KB ok
53 Correct 258 ms 258388 KB ok
54 Correct 232 ms 238676 KB ok
55 Correct 656 ms 513584 KB ok
56 Correct 193 ms 139092 KB ok
57 Correct 154 ms 89572 KB ok
58 Correct 121 ms 30036 KB ok
59 Correct 157 ms 99676 KB ok
60 Correct 234 ms 216144 KB ok
61 Correct 140 ms 71248 KB ok
62 Correct 243 ms 264268 KB ok
63 Correct 248 ms 262736 KB ok
64 Correct 230 ms 253916 KB ok
65 Execution timed out 4602 ms 112564 KB Time limit exceeded
66 Halted 0 ms 0 KB -