oj.uz

Submission #1011947

# Submission time Handle Problem Language Result Execution time Memory
1011947 2024-07-01T11:36:01 Z mdn2002 Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 458652 KB 
#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int dp[8000006];
int biggest_stadium(int N, vector<vector<int>> F) {
    memset(dp, -1, sizeof dp);
    int n = N;
    vector<vector<int>> a = F, next(n, vector<int>(n)), sum(n, vector<int>(n));
    map<vector<int>, int> mp;

    function<int(int, int, int, int)> summ = [&] (int l, int r, int x, int y) {
        long long ans = sum[y][r];
        if (x - 1 >= 0) ans -= sum[x - 1][r];
        if (l - 1 >= 0) ans -= sum[y][l - 1];
        if (x - 1 >= 0 && l - 1 >= 0) ans += sum[x - 1][l - 1];
        return ans;
    };
    
    int cnt = 0;
    function<int(int, int, int, int)> f = [&] (int l, int r, int x, int y) {
        if (mp.count({l, r, x, y}) == 0) mp[{l, r, x, y}] = ++ cnt;
        int ans = 0, id = mp[{l, r, x, y}];
        if (dp[id] != -1) return dp[id];
        if (x - 1 >= 0) {
            for (int j = l; j <= r; j ++) {
                if (a[x - 1][j]) continue;
                int z = min(r, next[x - 1][j]);
                int ll = 0, rr = x, mid;
                while (ll < rr) {
                    mid = (ll + rr) / 2;
                    if (summ(j, z, mid, y) == 0) rr = mid;
                    else ll = mid + 1;
                }
                ans = max(ans, f(j, z, ll, y) + (z - j + 1) * (x - ll));
                j = z;
            }
        }
        if (y + 1 < n) {
            for (int j = l; j <= r; j ++) {
                if (a[y + 1][j]) continue;
                int z = min(r, next[y + 1][j]);
                int ll = y + 1, rr = n, mid;
                while (ll < rr) {
                    mid = (ll + rr) / 2;
                    if (summ(j, z, x, mid) == 0) ll = mid + 1;
                    else rr = mid;
                }
                ll --;
                ans = max(ans, f(j, z, x, ll) + (z - j + 1) * (ll - y));
                j = z;
            }
        }

        return dp[id] = ans;
    };

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            sum[i][j] += a[i][j];
            if (j) sum[i][j] += sum[i][j - 1];
        }
    }
    for (int i = 1; i < n; i ++) {
        for (int j = 0; j < n; j ++) sum[i][j] += sum[i - 1][j];
    }
    for (int i = 0; i < n; i ++) {
        if (a[i][n - 1] == 0) next[i][n - 1] = n - 1;
        else next[i][n - 1] = n - 2;
        for (int j = n - 2; j >= 0; j --) {
            if (a[i][j]) next[i][j] = j - 1;
            else next[i][j] = next[i][j + 1];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (a[i][j]) continue;
            int ll = i, rr = n, mid, x, y;
            while (ll < rr) {
                mid = (ll + rr) / 2;
                if (summ(j, next[i][j], i, mid) == 0) ll = mid + 1;
                else rr = mid;
            }
            ll --;
            y = ll;

            ll = 0, rr = i;
            while (ll < rr) {
                mid = (ll + rr) / 2;
                if (summ(j, next[i][j], mid, i) == 0) rr = mid;
                else ll = mid + 1;
            }
            x = ll;
            ans = max(ans, f(j, next[i][j], x, y) + (next[i][j] - j + 1) * (y - x + 1));
            j = next[i][j];
        }
    }
    return ans;
}
/*
3
0 0 0
0 1 0
0 0 0
*/

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31580 KB ok
2 Correct 11 ms 31544 KB ok
3 Correct 11 ms 31576 KB ok
4 Correct 13 ms 31580 KB ok
5 Correct 12 ms 31632 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 13 ms 31764 KB ok
8 Correct 27 ms 37208 KB ok
9 Correct 235 ms 116556 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31580 KB ok
2 Correct 11 ms 31544 KB ok
3 Correct 12 ms 31580 KB ok
4 Correct 13 ms 31664 KB ok
5 Correct 12 ms 31576 KB ok
6 Correct 12 ms 31576 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 12 ms 31580 KB ok
9 Correct 12 ms 31576 KB ok
10 Correct 12 ms 31580 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 12 ms 31580 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok
2 Correct 11 ms 31580 KB ok
3 Correct 11 ms 31544 KB ok
4 Correct 12 ms 31580 KB ok
5 Correct 13 ms 31664 KB ok
6 Correct 12 ms 31576 KB ok
7 Correct 12 ms 31576 KB ok
8 Correct 12 ms 31580 KB ok
9 Correct 12 ms 31580 KB ok
10 Correct 12 ms 31576 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 12 ms 31580 KB ok
13 Correct 13 ms 31580 KB ok
14 Correct 12 ms 31580 KB ok
15 Correct 15 ms 31580 KB ok
16 Correct 13 ms 31580 KB ok
17 Correct 12 ms 31580 KB ok
18 Correct 16 ms 31580 KB ok
19 Correct 13 ms 31576 KB ok
20 Correct 12 ms 31548 KB ok
21 Correct 12 ms 31580 KB ok
22 Correct 14 ms 31676 KB ok
23 Correct 12 ms 31576 KB ok
24 Correct 12 ms 31580 KB ok
25 Correct 12 ms 31720 KB ok
26 Correct 13 ms 31576 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok
2 Correct 11 ms 31580 KB ok
3 Correct 11 ms 31544 KB ok
4 Correct 11 ms 31576 KB ok
5 Correct 13 ms 31580 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 13 ms 31664 KB ok
8 Correct 12 ms 31576 KB ok
9 Correct 12 ms 31576 KB ok
10 Correct 12 ms 31580 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 12 ms 31576 KB ok
13 Correct 12 ms 31580 KB ok
14 Correct 12 ms 31580 KB ok
15 Correct 13 ms 31580 KB ok
16 Correct 12 ms 31580 KB ok
17 Correct 15 ms 31580 KB ok
18 Correct 13 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 16 ms 31580 KB ok
21 Correct 13 ms 31576 KB ok
22 Correct 12 ms 31548 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 14 ms 31676 KB ok
25 Correct 12 ms 31576 KB ok
26 Correct 12 ms 31580 KB ok
27 Correct 12 ms 31720 KB ok
28 Correct 13 ms 31576 KB ok
29 Correct 12 ms 31580 KB ok
30 Correct 12 ms 31580 KB ok
31 Correct 12 ms 31824 KB ok
32 Correct 12 ms 31580 KB ok
33 Correct 15 ms 31944 KB ok
34 Correct 14 ms 31580 KB ok
35 Correct 12 ms 31628 KB ok
36 Correct 14 ms 31720 KB ok
37 Correct 12 ms 31580 KB ok
38 Correct 14 ms 31680 KB ok
39 Correct 12 ms 31580 KB ok
40 Correct 12 ms 31628 KB ok
41 Correct 12 ms 31580 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok
2 Correct 11 ms 31580 KB ok
3 Correct 11 ms 31544 KB ok
4 Correct 11 ms 31576 KB ok
5 Correct 13 ms 31580 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 13 ms 31664 KB ok
8 Correct 12 ms 31576 KB ok
9 Correct 12 ms 31576 KB ok
10 Correct 12 ms 31580 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 12 ms 31576 KB ok
13 Correct 12 ms 31580 KB ok
14 Correct 12 ms 31580 KB ok
15 Correct 13 ms 31580 KB ok
16 Correct 12 ms 31580 KB ok
17 Correct 15 ms 31580 KB ok
18 Correct 13 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 16 ms 31580 KB ok
21 Correct 13 ms 31576 KB ok
22 Correct 12 ms 31548 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 14 ms 31676 KB ok
25 Correct 12 ms 31576 KB ok
26 Correct 12 ms 31580 KB ok
27 Correct 12 ms 31720 KB ok
28 Correct 13 ms 31576 KB ok
29 Correct 12 ms 31580 KB ok
30 Correct 12 ms 31580 KB ok
31 Correct 12 ms 31824 KB ok
32 Correct 12 ms 31580 KB ok
33 Correct 15 ms 31944 KB ok
34 Correct 14 ms 31580 KB ok
35 Correct 12 ms 31628 KB ok
36 Correct 14 ms 31720 KB ok
37 Correct 12 ms 31580 KB ok
38 Correct 14 ms 31680 KB ok
39 Correct 12 ms 31580 KB ok
40 Correct 12 ms 31628 KB ok
41 Correct 12 ms 31580 KB ok
42 Correct 336 ms 62544 KB ok
43 Correct 223 ms 56144 KB ok
44 Correct 402 ms 68544 KB ok
45 Correct 341 ms 63572 KB ok
46 Correct 354 ms 67668 KB ok
47 Correct 26 ms 37200 KB ok
48 Correct 55 ms 40280 KB ok
49 Correct 51 ms 40020 KB ok
50 Correct 134 ms 50812 KB ok
51 Correct 45 ms 39508 KB ok
52 Correct 39 ms 39004 KB ok
53 Correct 27 ms 37332 KB ok
54 Correct 38 ms 38792 KB ok
55 Correct 48 ms 39664 KB ok
56 Correct 27 ms 37208 KB ok
57 Correct 65 ms 44112 KB ok
58 Correct 70 ms 45136 KB ok
59 Correct 81 ms 45904 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok
2 Correct 11 ms 31580 KB ok
3 Correct 11 ms 31544 KB ok
4 Correct 11 ms 31576 KB ok
5 Correct 13 ms 31580 KB ok
6 Correct 12 ms 31632 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 13 ms 31764 KB ok
9 Correct 27 ms 37208 KB ok
10 Correct 235 ms 116556 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 13 ms 31664 KB ok
13 Correct 12 ms 31576 KB ok
14 Correct 12 ms 31576 KB ok
15 Correct 12 ms 31580 KB ok
16 Correct 12 ms 31580 KB ok
17 Correct 12 ms 31576 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 13 ms 31580 KB ok
21 Correct 12 ms 31580 KB ok
22 Correct 15 ms 31580 KB ok
23 Correct 13 ms 31580 KB ok
24 Correct 12 ms 31580 KB ok
25 Correct 16 ms 31580 KB ok
26 Correct 13 ms 31576 KB ok
27 Correct 12 ms 31548 KB ok
28 Correct 12 ms 31580 KB ok
29 Correct 14 ms 31676 KB ok
30 Correct 12 ms 31576 KB ok
31 Correct 12 ms 31580 KB ok
32 Correct 12 ms 31720 KB ok
33 Correct 13 ms 31576 KB ok
34 Correct 12 ms 31580 KB ok
35 Correct 12 ms 31580 KB ok
36 Correct 12 ms 31824 KB ok
37 Correct 12 ms 31580 KB ok
38 Correct 15 ms 31944 KB ok
39 Correct 14 ms 31580 KB ok
40 Correct 12 ms 31628 KB ok
41 Correct 14 ms 31720 KB ok
42 Correct 12 ms 31580 KB ok
43 Correct 14 ms 31680 KB ok
44 Correct 12 ms 31580 KB ok
45 Correct 12 ms 31628 KB ok
46 Correct 12 ms 31580 KB ok
47 Correct 336 ms 62544 KB ok
48 Correct 223 ms 56144 KB ok
49 Correct 402 ms 68544 KB ok
50 Correct 341 ms 63572 KB ok
51 Correct 354 ms 67668 KB ok
52 Correct 26 ms 37200 KB ok
53 Correct 55 ms 40280 KB ok
54 Correct 51 ms 40020 KB ok
55 Correct 134 ms 50812 KB ok
56 Correct 45 ms 39508 KB ok
57 Correct 39 ms 39004 KB ok
58 Correct 27 ms 37332 KB ok
59 Correct 38 ms 38792 KB ok
60 Correct 48 ms 39664 KB ok
61 Correct 27 ms 37208 KB ok
62 Correct 65 ms 44112 KB ok
63 Correct 70 ms 45136 KB ok
64 Correct 81 ms 45904 KB ok
65 Execution timed out 4551 ms 458652 KB Time limit exceeded
66 Halted 0 ms 0 KB -