oj.uz

Submission #840055

# Submission time Handle Problem Language Result Execution time Memory
840055 2023-08-31T03:25:13 Z olnyfcxwps Soccer Stadium (IOI23_soccer) C++17
29.5 / 100
 657 ms 540656 KB 
#include <iostream>
#include <vector>
using namespace std;

const int N = 30;
int n;
int tree[2000][2000];
bool seen[2000][2000];
int prefix[N][N];
int dp1[N][N][N];
int dp2[N][N][N];

bool are_empty(int row, int col1, int col2) {
    if (col1 == 0) {
        return prefix[row][col2] == 0;
    }
    return prefix[row][col2] == prefix[row][col1 - 1];
}

int solve_1() {
    int x = 0;
    int y = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (tree[i][j] == 1) {
                x = i;
                y = j;
            }
        }
    }
    x += 1;
    y += 1;
    int m = x * y;
    int t = x * (n - y + 1);
    if (t < m) {
        m = t;
    }
    t = (n - x + 1) * y;
    if (t < m) {
        m = t;
    }
    t = (n - x + 1) * (n - y + 1);
    if (t < m) {
        m = t;
    }
    return n * n - m;
}

int dp() {
    // init
    for (int i = 0; i < n; i++) {
        prefix[i][0] = tree[i][0];
        for (int j = 1; j < n; j++) {
            prefix[i][j] = prefix[i][j - 1] + tree[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                dp1[i][j][k] = -1;
                dp2[i][j][k] = -1;
            }
        }
    }
    for (int j = 0; j < n; j++) {
        for (int k = j; k < n; k++) {
            // if all empty
            if (are_empty(0, j, k)) {
                dp1[0][j][k] = k - j + 1;
            }
        }
    }

    // dp from 1 to n - 1
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = j; k < n; k++) {
                // check base case
                if (are_empty(i, j, k)) {
                    dp1[i][j][k] = k - j + 1;
                } else {
                    continue;
                }
                for (int l = j; l <= k; l++) {
                    for (int m = l; m <= k; m++) {
                        // check if [l, m] are all empty
                        if (!are_empty(i - 1, l, m)) {
                            break;
                        }
                        // dp1
                        if (dp1[i - 1][l][m] != -1) {
                            int t = dp1[i - 1][l][m] + k - j + 1;
                            if (dp1[i][j][k] == -1 || dp1[i][j][k] < t) {
                                dp1[i][j][k] = t;
                            }
                        }
                    }
                }
            }
        }
    }

    for (int j = 0; j < n; j++) {
        for (int k = j; k < n; k++) {
            // if all empty
            if (are_empty(n - 1, j, k)) {
                dp2[n - 1][j][k] = k - j + 1;
            }
        }
    }

    // dp from n - 2 to 0
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            for (int k = j; k < n; k++) {
                // check base case
                if (are_empty(i, j, k)) {
                    dp2[i][j][k] = k - j + 1;
                } else {
                    continue;
                }
                for (int l = j; l <= k; l++) {
                    for (int m = l; m <= k; m++) {
                        // check if [l, m] are all empty
                        if (!are_empty(i + 1, l, m)) {
                            break;
                        }
                        // dp2
                        if (dp2[i + 1][l][m] != -1) {
                            int t = dp2[i + 1][l][m] + k - j + 1;
                            if (dp2[i][j][k] == -1 || dp2[i][j][k] < t) {
                                dp2[i][j][k] = t;
                            }
                        }
                    }
                }
            }
        }
    }

    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = j; k < n; k++) {
                cout << i << " " << j << " " << k << " " << dp1[i][j][k] << "\n";
            }
        }
    }*/

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = j; k < n; k++) {
                if (ans < dp1[i][j][k]) {
                    ans = dp1[i][j][k];
                }
                if (ans < dp2[i][j][k]) {
                    ans = dp2[i][j][k];
                }
                /*if (dp1[i][j][k] != -1 && dp2[i][j][k] != -1) {
                    int t = dp1[i][j][k] + dp2[i][j][k] - (k - j + 1);
                    if (t > ans) {
                        ans = t;
                    }
                }*/
            }
        }
    }

    return ans;
}

void dfs(int r, int c) {
    seen[r][c] = true;
    if (r - 1 >= 0 && tree[r - 1][c] == 0 && !seen[r - 1][c]) {
        dfs(r - 1, c);
    }
    if (r + 1 < n && tree[r + 1][c] == 0 && !seen[r + 1][c]) {
        dfs(r + 1, c);
    }
    if (c - 1 >= 0 && tree[r][c - 1] == 0 && !seen[r][c - 1]) {
        dfs(r, c - 1);
    }
    if (c + 1 < n && tree[r][c + 1] == 0 && !seen[r][c + 1]) {
        dfs(r, c + 1);
    }
}

bool check() {
    int c = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            seen[i][j] = false;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (tree[i][j] == 0) {
                if (!seen[i][j]) {
                    dfs(i, j);
                    c += 1;
                }
            }
        }
    }
    if (c != 1) {
        return false;
    }

    vector<int> s;
    vector<int> t;
    int longest = 0;
    int where = 0;
    for (int i = 0; i < n; i++) {
        bool seen = false;
        for (int j = 0; j < n;) {
            if (tree[i][j] == 0) {
                if (seen) {
                    return false;
                }
                seen = true;
                int k = j + 1;
                while (k < n && tree[i][k] == 0) {
                    k++;
                }
                s.push_back(j);
                t.push_back(k - 1);
                if (longest < k - j) {
                    longest = k - j;
                    where = s.size() - 1;
                }
                j = k;
            } else {
                j++;
            }
        }
    }

    /*for (int i = 0; i < s.size(); i++) {
        cout << s[i] << " " << t[i] << "\n";
    }
    cout << where << "\n";*/

    for (int i = where - 1; i >= 0; i--) {
        if (s[i] < s[i + 1] || t[i] > t[i + 1]) {
            return false;
        }
    }

    for (int i = where; i + 1 < s.size(); i++) {
        // cout << i << "\n";
        if (s[i + 1] < s[i] || t[i + 1] > t[i]) {
            return false;
        }
    }
    // cout << "here\n";

    for (int i = 0; i < s.size(); i++) {
        for (int j = i + 1; j < s.size(); j++) {
            if (!(s[i] <= s[j] && t[j] <= t[i]
                || s[j] <= s[i] && t[i] <= t[j]
            )) {
                return false;
            }
        }
    }

    return true;
}

// int biggest_stadium(int N, int[][] F)
int biggest_stadium(int X, vector<vector<int>> F) {
    n = X;
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tree[i][j] = F[i][j];
            total += tree[i][j];
        }
    }
    if (total == 1) {
        return solve_1();
    }
    if (total == 0) {
        return n * n;
    }
    /*if (n > 30) {
        return 123;
    }*/

    if (check()) {
        return n * n - total;
    }

    return 0;

    /*int ans = dp();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int t = tree[i][j];
            tree[i][j] = tree[j][i];
            tree[j][i] = t;
        }
    }
    int another_ans = dp();
    if (another_ans > ans) {
        ans = another_ans;
    }
    return ans;*/
}

Compilation message

soccer.cpp: In function 'bool check()':
soccer.cpp:249:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |     for (int i = where; i + 1 < s.size(); i++) {
      |                         ~~~~~~^~~~~~~~~~
soccer.cpp:257:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  257 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
soccer.cpp:258:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |         for (int j = i + 1; j < s.size(); j++) {
      |                             ~~^~~~~~~~~~
soccer.cpp:259:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  259 |             if (!(s[i] <= s[j] && t[j] <= t[i]

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 1 ms 724 KB ok
8 Correct 20 ms 5152 KB ok
9 Correct 307 ms 47388 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Partially correct 0 ms 340 KB partial
4 Partially correct 0 ms 340 KB partial
5 Partially correct 1 ms 212 KB partial
6 Partially correct 0 ms 340 KB partial
7 Partially correct 0 ms 340 KB partial
8 Correct 0 ms 340 KB ok
9 Correct 0 ms 212 KB ok
10 Partially correct 1 ms 212 KB partial
11 Partially correct 0 ms 212 KB partial
12 Partially correct 0 ms 212 KB partial
13 Correct 0 ms 340 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB partial
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Partially correct 0 ms 340 KB partial
5 Partially correct 0 ms 340 KB partial
6 Partially correct 1 ms 212 KB partial
7 Partially correct 0 ms 340 KB partial
8 Partially correct 0 ms 340 KB partial
9 Correct 0 ms 340 KB ok
10 Correct 0 ms 212 KB ok
11 Partially correct 1 ms 212 KB partial
12 Partially correct 0 ms 212 KB partial
13 Partially correct 0 ms 212 KB partial
14 Correct 0 ms 340 KB ok
15 Partially correct 0 ms 340 KB partial
16 Partially correct 0 ms 340 KB partial
17 Partially correct 0 ms 340 KB partial
18 Partially correct 0 ms 340 KB partial
19 Partially correct 0 ms 340 KB partial
20 Correct 0 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Partially correct 0 ms 340 KB partial
23 Partially correct 0 ms 340 KB partial
24 Partially correct 1 ms 340 KB partial
25 Partially correct 0 ms 340 KB partial
26 Partially correct 1 ms 340 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB partial
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Partially correct 0 ms 340 KB partial
7 Partially correct 0 ms 340 KB partial
8 Partially correct 1 ms 212 KB partial
9 Partially correct 0 ms 340 KB partial
10 Partially correct 0 ms 340 KB partial
11 Correct 0 ms 340 KB ok
12 Correct 0 ms 212 KB ok
13 Partially correct 1 ms 212 KB partial
14 Partially correct 0 ms 212 KB partial
15 Partially correct 0 ms 212 KB partial
16 Correct 0 ms 340 KB ok
17 Partially correct 0 ms 340 KB partial
18 Partially correct 0 ms 340 KB partial
19 Partially correct 0 ms 340 KB partial
20 Partially correct 0 ms 340 KB partial
21 Partially correct 0 ms 340 KB partial
22 Correct 0 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Partially correct 0 ms 340 KB partial
25 Partially correct 0 ms 340 KB partial
26 Partially correct 1 ms 340 KB partial
27 Partially correct 0 ms 340 KB partial
28 Partially correct 1 ms 340 KB partial
29 Partially correct 1 ms 340 KB partial
30 Partially correct 1 ms 468 KB partial
31 Partially correct 0 ms 468 KB partial
32 Partially correct 1 ms 468 KB partial
33 Partially correct 1 ms 468 KB partial
34 Correct 0 ms 468 KB ok
35 Correct 0 ms 468 KB ok
36 Partially correct 1 ms 468 KB partial
37 Partially correct 0 ms 468 KB partial
38 Partially correct 0 ms 468 KB partial
39 Partially correct 0 ms 468 KB partial
40 Partially correct 0 ms 468 KB partial
41 Partially correct 0 ms 468 KB partial

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB partial
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Partially correct 0 ms 340 KB partial
7 Partially correct 0 ms 340 KB partial
8 Partially correct 1 ms 212 KB partial
9 Partially correct 0 ms 340 KB partial
10 Partially correct 0 ms 340 KB partial
11 Correct 0 ms 340 KB ok
12 Correct 0 ms 212 KB ok
13 Partially correct 1 ms 212 KB partial
14 Partially correct 0 ms 212 KB partial
15 Partially correct 0 ms 212 KB partial
16 Correct 0 ms 340 KB ok
17 Partially correct 0 ms 340 KB partial
18 Partially correct 0 ms 340 KB partial
19 Partially correct 0 ms 340 KB partial
20 Partially correct 0 ms 340 KB partial
21 Partially correct 0 ms 340 KB partial
22 Correct 0 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Partially correct 0 ms 340 KB partial
25 Partially correct 0 ms 340 KB partial
26 Partially correct 1 ms 340 KB partial
27 Partially correct 0 ms 340 KB partial
28 Partially correct 1 ms 340 KB partial
29 Partially correct 1 ms 340 KB partial
30 Partially correct 1 ms 468 KB partial
31 Partially correct 0 ms 468 KB partial
32 Partially correct 1 ms 468 KB partial
33 Partially correct 1 ms 468 KB partial
34 Correct 0 ms 468 KB ok
35 Correct 0 ms 468 KB ok
36 Partially correct 1 ms 468 KB partial
37 Partially correct 0 ms 468 KB partial
38 Partially correct 0 ms 468 KB partial
39 Partially correct 0 ms 468 KB partial
40 Partially correct 0 ms 468 KB partial
41 Partially correct 0 ms 468 KB partial
42 Partially correct 33 ms 22176 KB partial
43 Partially correct 37 ms 17432 KB partial
44 Partially correct 34 ms 25928 KB partial
45 Partially correct 34 ms 26476 KB partial
46 Partially correct 34 ms 24596 KB partial
47 Partially correct 40 ms 36436 KB partial
48 Correct 28 ms 14364 KB ok
49 Partially correct 34 ms 16704 KB partial
50 Partially correct 32 ms 21740 KB partial
51 Partially correct 25 ms 10128 KB partial
52 Partially correct 21 ms 8348 KB partial
53 Partially correct 21 ms 7124 KB partial
54 Partially correct 21 ms 8476 KB partial
55 Partially correct 22 ms 9684 KB partial
56 Partially correct 29 ms 18840 KB partial
57 Partially correct 36 ms 29536 KB partial
58 Partially correct 39 ms 28184 KB partial
59 Partially correct 35 ms 26060 KB partial

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB partial
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 1 ms 724 KB ok
9 Correct 20 ms 5152 KB ok
10 Correct 307 ms 47388 KB ok
11 Partially correct 0 ms 340 KB partial
12 Partially correct 0 ms 340 KB partial
13 Partially correct 1 ms 212 KB partial
14 Partially correct 0 ms 340 KB partial
15 Partially correct 0 ms 340 KB partial
16 Correct 0 ms 340 KB ok
17 Correct 0 ms 212 KB ok
18 Partially correct 1 ms 212 KB partial
19 Partially correct 0 ms 212 KB partial
20 Partially correct 0 ms 212 KB partial
21 Correct 0 ms 340 KB ok
22 Partially correct 0 ms 340 KB partial
23 Partially correct 0 ms 340 KB partial
24 Partially correct 0 ms 340 KB partial
25 Partially correct 0 ms 340 KB partial
26 Partially correct 0 ms 340 KB partial
27 Correct 0 ms 340 KB ok
28 Correct 0 ms 340 KB ok
29 Partially correct 0 ms 340 KB partial
30 Partially correct 0 ms 340 KB partial
31 Partially correct 1 ms 340 KB partial
32 Partially correct 0 ms 340 KB partial
33 Partially correct 1 ms 340 KB partial
34 Partially correct 1 ms 340 KB partial
35 Partially correct 1 ms 468 KB partial
36 Partially correct 0 ms 468 KB partial
37 Partially correct 1 ms 468 KB partial
38 Partially correct 1 ms 468 KB partial
39 Correct 0 ms 468 KB ok
40 Correct 0 ms 468 KB ok
41 Partially correct 1 ms 468 KB partial
42 Partially correct 0 ms 468 KB partial
43 Partially correct 0 ms 468 KB partial
44 Partially correct 0 ms 468 KB partial
45 Partially correct 0 ms 468 KB partial
46 Partially correct 0 ms 468 KB partial
47 Partially correct 33 ms 22176 KB partial
48 Partially correct 37 ms 17432 KB partial
49 Partially correct 34 ms 25928 KB partial
50 Partially correct 34 ms 26476 KB partial
51 Partially correct 34 ms 24596 KB partial
52 Partially correct 40 ms 36436 KB partial
53 Correct 28 ms 14364 KB ok
54 Partially correct 34 ms 16704 KB partial
55 Partially correct 32 ms 21740 KB partial
56 Partially correct 25 ms 10128 KB partial
57 Partially correct 21 ms 8348 KB partial
58 Partially correct 21 ms 7124 KB partial
59 Partially correct 21 ms 8476 KB partial
60 Partially correct 22 ms 9684 KB partial
61 Partially correct 29 ms 18840 KB partial
62 Partially correct 36 ms 29536 KB partial
63 Partially correct 39 ms 28184 KB partial
64 Partially correct 35 ms 26060 KB partial
65 Partially correct 522 ms 307996 KB partial
66 Partially correct 350 ms 51228 KB partial
67 Partially correct 321 ms 51328 KB partial
68 Partially correct 523 ms 361816 KB partial
69 Partially correct 539 ms 369388 KB partial
70 Partially correct 502 ms 363212 KB partial
71 Partially correct 535 ms 387352 KB partial
72 Partially correct 657 ms 540656 KB partial
73 Correct 436 ms 179220 KB ok
74 Correct 441 ms 183636 KB ok
75 Partially correct 438 ms 183324 KB partial
76 Partially correct 484 ms 301504 KB partial
77 Partially correct 482 ms 300500 KB partial
78 Partially correct 428 ms 116144 KB partial
79 Partially correct 322 ms 51228 KB partial
80 Partially correct 319 ms 51336 KB partial
81 Partially correct 314 ms 51488 KB partial
82 Partially correct 331 ms 51868 KB partial
83 Partially correct 329 ms 51236 KB partial
84 Partially correct 341 ms 74828 KB partial
85 Partially correct 312 ms 65540 KB partial
86 Partially correct 353 ms 86684 KB partial
87 Partially correct 362 ms 103592 KB partial
88 Partially correct 438 ms 252704 KB partial
89 Partially correct 609 ms 502604 KB partial
90 Partially correct 529 ms 367336 KB partial
91 Partially correct 513 ms 272028 KB partial
92 Partially correct 323 ms 51228 KB partial
93 Partially correct 322 ms 51324 KB partial
94 Partially correct 316 ms 51328 KB partial
95 Partially correct 321 ms 51240 KB partial
96 Partially correct 311 ms 51232 KB partial
97 Partially correct 308 ms 51276 KB partial
98 Partially correct 309 ms 51256 KB partial
99 Partially correct 370 ms 67356 KB partial
100 Partially correct 574 ms 426444 KB partial
101 Partially correct 553 ms 257436 KB partial
102 Partially correct 585 ms 239240 KB partial
103 Partially correct 566 ms 400236 KB partial
104 Partially correct 555 ms 250920 KB partial
105 Partially correct 552 ms 251684 KB partial
106 Partially correct 572 ms 340044 KB partial
107 Partially correct 566 ms 306268 KB partial
108 Partially correct 392 ms 68132 KB partial
109 Partially correct 392 ms 81992 KB partial