oj.uz

Submission #1011933

# Submission time Handle Problem Language Result Execution time Memory
1011933 2024-07-01T11:17:17 Z mdn2002 Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 382976 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;
        if (dp[mp[{l, r, x, y}]] != -1) return dp[mp[{l, r, x, y}]];
        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[mp[{l, r, x, y}]] = 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 31576 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31580 KB ok
2 Correct 13 ms 31580 KB ok
3 Correct 14 ms 31608 KB ok
4 Correct 13 ms 31592 KB ok
5 Correct 17 ms 31672 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 18 ms 31836 KB ok
8 Correct 26 ms 36516 KB ok
9 Correct 223 ms 110164 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31580 KB ok
2 Correct 13 ms 31580 KB ok
3 Correct 12 ms 31520 KB ok
4 Correct 14 ms 31520 KB ok
5 Correct 11 ms 31596 KB ok
6 Correct 13 ms 31576 KB ok
7 Correct 13 ms 31580 KB ok
8 Correct 12 ms 31576 KB ok
9 Correct 12 ms 31580 KB ok
10 Correct 13 ms 31580 KB ok
11 Correct 11 ms 31696 KB ok
12 Correct 12 ms 31576 KB ok
13 Correct 12 ms 31604 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 14 ms 31580 KB ok
3 Correct 13 ms 31580 KB ok
4 Correct 12 ms 31520 KB ok
5 Correct 14 ms 31520 KB ok
6 Correct 11 ms 31596 KB ok
7 Correct 13 ms 31576 KB ok
8 Correct 13 ms 31580 KB ok
9 Correct 12 ms 31576 KB ok
10 Correct 12 ms 31580 KB ok
11 Correct 13 ms 31580 KB ok
12 Correct 11 ms 31696 KB ok
13 Correct 12 ms 31576 KB ok
14 Correct 12 ms 31604 KB ok
15 Correct 13 ms 31580 KB ok
16 Correct 12 ms 31580 KB ok
17 Correct 12 ms 31580 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 15 ms 31576 KB ok
20 Correct 13 ms 31580 KB ok
21 Correct 13 ms 31580 KB ok
22 Correct 12 ms 31516 KB ok
23 Correct 13 ms 31580 KB ok
24 Correct 16 ms 31740 KB ok
25 Correct 12 ms 31528 KB ok
26 Correct 14 ms 31576 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 14 ms 31580 KB ok
3 Correct 13 ms 31580 KB ok
4 Correct 14 ms 31608 KB ok
5 Correct 13 ms 31592 KB ok
6 Correct 12 ms 31520 KB ok
7 Correct 14 ms 31520 KB ok
8 Correct 11 ms 31596 KB ok
9 Correct 13 ms 31576 KB ok
10 Correct 13 ms 31580 KB ok
11 Correct 12 ms 31576 KB ok
12 Correct 12 ms 31580 KB ok
13 Correct 13 ms 31580 KB ok
14 Correct 11 ms 31696 KB ok
15 Correct 12 ms 31576 KB ok
16 Correct 12 ms 31604 KB ok
17 Correct 13 ms 31580 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 12 ms 31580 KB ok
21 Correct 15 ms 31576 KB ok
22 Correct 13 ms 31580 KB ok
23 Correct 13 ms 31580 KB ok
24 Correct 12 ms 31516 KB ok
25 Correct 13 ms 31580 KB ok
26 Correct 16 ms 31740 KB ok
27 Correct 12 ms 31528 KB ok
28 Correct 14 ms 31576 KB ok
29 Correct 18 ms 31580 KB ok
30 Correct 15 ms 31584 KB ok
31 Correct 17 ms 31700 KB ok
32 Correct 10 ms 31576 KB ok
33 Correct 11 ms 31760 KB ok
34 Correct 12 ms 31772 KB ok
35 Correct 10 ms 31580 KB ok
36 Correct 13 ms 31744 KB ok
37 Correct 13 ms 31580 KB ok
38 Correct 13 ms 31684 KB ok
39 Correct 11 ms 31832 KB ok
40 Correct 11 ms 31724 KB ok
41 Correct 18 ms 31580 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 14 ms 31580 KB ok
3 Correct 13 ms 31580 KB ok
4 Correct 14 ms 31608 KB ok
5 Correct 13 ms 31592 KB ok
6 Correct 12 ms 31520 KB ok
7 Correct 14 ms 31520 KB ok
8 Correct 11 ms 31596 KB ok
9 Correct 13 ms 31576 KB ok
10 Correct 13 ms 31580 KB ok
11 Correct 12 ms 31576 KB ok
12 Correct 12 ms 31580 KB ok
13 Correct 13 ms 31580 KB ok
14 Correct 11 ms 31696 KB ok
15 Correct 12 ms 31576 KB ok
16 Correct 12 ms 31604 KB ok
17 Correct 13 ms 31580 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 12 ms 31580 KB ok
21 Correct 15 ms 31576 KB ok
22 Correct 13 ms 31580 KB ok
23 Correct 13 ms 31580 KB ok
24 Correct 12 ms 31516 KB ok
25 Correct 13 ms 31580 KB ok
26 Correct 16 ms 31740 KB ok
27 Correct 12 ms 31528 KB ok
28 Correct 14 ms 31576 KB ok
29 Correct 18 ms 31580 KB ok
30 Correct 15 ms 31584 KB ok
31 Correct 17 ms 31700 KB ok
32 Correct 10 ms 31576 KB ok
33 Correct 11 ms 31760 KB ok
34 Correct 12 ms 31772 KB ok
35 Correct 10 ms 31580 KB ok
36 Correct 13 ms 31744 KB ok
37 Correct 13 ms 31580 KB ok
38 Correct 13 ms 31684 KB ok
39 Correct 11 ms 31832 KB ok
40 Correct 11 ms 31724 KB ok
41 Correct 18 ms 31580 KB ok
42 Correct 392 ms 61972 KB ok
43 Correct 292 ms 55700 KB ok
44 Correct 510 ms 68008 KB ok
45 Correct 436 ms 62968 KB ok
46 Correct 519 ms 66964 KB ok
47 Correct 27 ms 36700 KB ok
48 Correct 64 ms 39760 KB ok
49 Correct 59 ms 39704 KB ok
50 Correct 186 ms 50260 KB ok
51 Correct 49 ms 38840 KB ok
52 Correct 45 ms 38480 KB ok
53 Correct 29 ms 36956 KB ok
54 Correct 70 ms 38112 KB ok
55 Correct 58 ms 38996 KB ok
56 Correct 27 ms 36768 KB ok
57 Correct 83 ms 43536 KB ok
58 Correct 99 ms 44628 KB ok
59 Correct 110 ms 45456 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 14 ms 31580 KB ok
3 Correct 13 ms 31580 KB ok
4 Correct 14 ms 31608 KB ok
5 Correct 13 ms 31592 KB ok
6 Correct 17 ms 31672 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 18 ms 31836 KB ok
9 Correct 26 ms 36516 KB ok
10 Correct 223 ms 110164 KB ok
11 Correct 12 ms 31520 KB ok
12 Correct 14 ms 31520 KB ok
13 Correct 11 ms 31596 KB ok
14 Correct 13 ms 31576 KB ok
15 Correct 13 ms 31580 KB ok
16 Correct 12 ms 31576 KB ok
17 Correct 12 ms 31580 KB ok
18 Correct 13 ms 31580 KB ok
19 Correct 11 ms 31696 KB ok
20 Correct 12 ms 31576 KB ok
21 Correct 12 ms 31604 KB ok
22 Correct 13 ms 31580 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 12 ms 31580 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 15 ms 31576 KB ok
27 Correct 13 ms 31580 KB ok
28 Correct 13 ms 31580 KB ok
29 Correct 12 ms 31516 KB ok
30 Correct 13 ms 31580 KB ok
31 Correct 16 ms 31740 KB ok
32 Correct 12 ms 31528 KB ok
33 Correct 14 ms 31576 KB ok
34 Correct 18 ms 31580 KB ok
35 Correct 15 ms 31584 KB ok
36 Correct 17 ms 31700 KB ok
37 Correct 10 ms 31576 KB ok
38 Correct 11 ms 31760 KB ok
39 Correct 12 ms 31772 KB ok
40 Correct 10 ms 31580 KB ok
41 Correct 13 ms 31744 KB ok
42 Correct 13 ms 31580 KB ok
43 Correct 13 ms 31684 KB ok
44 Correct 11 ms 31832 KB ok
45 Correct 11 ms 31724 KB ok
46 Correct 18 ms 31580 KB ok
47 Correct 392 ms 61972 KB ok
48 Correct 292 ms 55700 KB ok
49 Correct 510 ms 68008 KB ok
50 Correct 436 ms 62968 KB ok
51 Correct 519 ms 66964 KB ok
52 Correct 27 ms 36700 KB ok
53 Correct 64 ms 39760 KB ok
54 Correct 59 ms 39704 KB ok
55 Correct 186 ms 50260 KB ok
56 Correct 49 ms 38840 KB ok
57 Correct 45 ms 38480 KB ok
58 Correct 29 ms 36956 KB ok
59 Correct 70 ms 38112 KB ok
60 Correct 58 ms 38996 KB ok
61 Correct 27 ms 36768 KB ok
62 Correct 83 ms 43536 KB ok
63 Correct 99 ms 44628 KB ok
64 Correct 110 ms 45456 KB ok
65 Execution timed out 4520 ms 382976 KB Time limit exceeded
66 Halted 0 ms 0 KB -