oj.uz

Submission #1076907

# Submission time Handle Problem Language Result Execution time Memory
1076907 2024-08-26T18:48:09 Z mickey080929 Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 513360 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) {
    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:35: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]
   35 |         for (int j=0; j<ran[i][i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~~~
soccer.cpp:44: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]
   44 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~
soccer.cpp:51: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]
   51 |             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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 3 ms 6544 KB ok
3 Correct 3 ms 6604 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 11 ms 16988 KB ok
8 Correct 263 ms 264320 KB ok
9 Execution timed out 4554 ms 75860 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB ok
2 Correct 3 ms 6544 KB ok
3 Correct 3 ms 6488 KB ok
4 Correct 2 ms 6492 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6488 KB ok
7 Correct 3 ms 6488 KB ok
8 Correct 3 ms 6488 KB ok
9 Correct 3 ms 6492 KB ok
10 Correct 3 ms 6492 KB ok
11 Correct 3 ms 6532 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 6488 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 3 ms 6544 KB ok
4 Correct 3 ms 6488 KB ok
5 Correct 2 ms 6492 KB ok
6 Correct 3 ms 6492 KB ok
7 Correct 3 ms 6488 KB ok
8 Correct 3 ms 6488 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 3 ms 6532 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 6488 KB ok
19 Correct 3 ms 6556 KB ok
20 Correct 2 ms 6492 KB ok
21 Correct 3 ms 6492 KB ok
22 Correct 3 ms 6492 KB ok
23 Correct 2 ms 6492 KB ok
24 Correct 2 ms 6492 KB ok
25 Correct 2 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 3 ms 6544 KB ok
4 Correct 3 ms 6604 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6488 KB ok
7 Correct 2 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 6488 KB ok
12 Correct 3 ms 6492 KB ok
13 Correct 3 ms 6492 KB ok
14 Correct 3 ms 6532 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 6488 KB ok
21 Correct 3 ms 6556 KB ok
22 Correct 2 ms 6492 KB ok
23 Correct 3 ms 6492 KB ok
24 Correct 3 ms 6492 KB ok
25 Correct 2 ms 6492 KB ok
26 Correct 2 ms 6492 KB ok
27 Correct 2 ms 6492 KB ok
28 Correct 2 ms 6492 KB ok
29 Correct 3 ms 6488 KB ok
30 Correct 6 ms 7516 KB ok
31 Correct 3 ms 7260 KB ok
32 Correct 3 ms 6828 KB ok
33 Correct 3 ms 6488 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 6748 KB ok
39 Correct 3 ms 7004 KB ok
40 Correct 4 ms 7260 KB ok
41 Correct 4 ms 7512 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 3 ms 6544 KB ok
4 Correct 3 ms 6604 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 3 ms 6488 KB ok
7 Correct 2 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 6488 KB ok
12 Correct 3 ms 6492 KB ok
13 Correct 3 ms 6492 KB ok
14 Correct 3 ms 6532 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 6488 KB ok
21 Correct 3 ms 6556 KB ok
22 Correct 2 ms 6492 KB ok
23 Correct 3 ms 6492 KB ok
24 Correct 3 ms 6492 KB ok
25 Correct 2 ms 6492 KB ok
26 Correct 2 ms 6492 KB ok
27 Correct 2 ms 6492 KB ok
28 Correct 2 ms 6492 KB ok
29 Correct 3 ms 6488 KB ok
30 Correct 6 ms 7516 KB ok
31 Correct 3 ms 7260 KB ok
32 Correct 3 ms 6828 KB ok
33 Correct 3 ms 6488 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 6748 KB ok
39 Correct 3 ms 7004 KB ok
40 Correct 4 ms 7260 KB ok
41 Correct 4 ms 7512 KB ok
42 Correct 193 ms 80720 KB ok
43 Correct 216 ms 45924 KB ok
44 Correct 363 ms 350544 KB ok
45 Correct 451 ms 377940 KB ok
46 Correct 237 ms 164948 KB ok
47 Correct 268 ms 270416 KB ok
48 Correct 257 ms 258388 KB ok
49 Correct 246 ms 238480 KB ok
50 Correct 660 ms 513360 KB ok
51 Correct 210 ms 139088 KB ok
52 Correct 170 ms 89680 KB ok
53 Correct 112 ms 29948 KB ok
54 Correct 153 ms 99664 KB ok
55 Correct 243 ms 216044 KB ok
56 Correct 140 ms 71248 KB ok
57 Correct 255 ms 264272 KB ok
58 Correct 241 ms 262740 KB ok
59 Correct 240 ms 253960 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB ok
2 Correct 3 ms 6492 KB ok
3 Correct 3 ms 6544 KB ok
4 Correct 3 ms 6604 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 11 ms 16988 KB ok
9 Correct 263 ms 264320 KB ok
10 Execution timed out 4554 ms 75860 KB Time limit exceeded
11 Halted 0 ms 0 KB -