oj.uz

Submission #1011928

# Submission time Handle Problem Language Result Execution time Memory
1011928 2024-07-01T11:15:28 Z mdn2002 Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 415520 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;
            while (ll < rr) {
                mid = (ll + rr) / 2;
                if (summ(j, next[i][j], i, mid) == 0) ll = mid + 1;
                else rr = mid;
            }
            ll --;
            ans = max(ans, f(j, next[i][j], i, ll) + (next[i][j] - j + 1) * (ll - i + 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 13 ms 31580 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok
2 Correct 13 ms 31720 KB ok
3 Correct 11 ms 31580 KB ok
4 Correct 12 ms 31580 KB ok
5 Correct 12 ms 31748 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 13 ms 31836 KB ok
8 Correct 27 ms 37264 KB ok
9 Correct 224 ms 117040 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB ok
2 Correct 13 ms 31720 KB ok
3 Correct 16 ms 31576 KB ok
4 Correct 12 ms 31580 KB ok
5 Correct 12 ms 31624 KB ok
6 Correct 13 ms 31576 KB ok
7 Correct 13 ms 31576 KB ok
8 Correct 13 ms 31580 KB ok
9 Correct 13 ms 31580 KB ok
10 Correct 15 ms 31580 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 14 ms 31636 KB ok
13 Correct 12 ms 31704 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31580 KB ok
2 Correct 12 ms 31580 KB ok
3 Correct 13 ms 31720 KB ok
4 Correct 16 ms 31576 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 12 ms 31624 KB ok
7 Correct 13 ms 31576 KB ok
8 Correct 13 ms 31576 KB ok
9 Correct 13 ms 31580 KB ok
10 Correct 13 ms 31580 KB ok
11 Correct 15 ms 31580 KB ok
12 Correct 12 ms 31580 KB ok
13 Correct 14 ms 31636 KB ok
14 Correct 12 ms 31704 KB ok
15 Correct 12 ms 31580 KB ok
16 Correct 13 ms 31580 KB ok
17 Correct 12 ms 31696 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 11 ms 31628 KB ok
21 Correct 12 ms 31580 KB ok
22 Correct 12 ms 31684 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 12 ms 31732 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 12 ms 31580 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31580 KB ok
2 Correct 12 ms 31580 KB ok
3 Correct 13 ms 31720 KB ok
4 Correct 11 ms 31580 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 16 ms 31576 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 12 ms 31624 KB ok
9 Correct 13 ms 31576 KB ok
10 Correct 13 ms 31576 KB ok
11 Correct 13 ms 31580 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 15 ms 31580 KB ok
14 Correct 12 ms 31580 KB ok
15 Correct 14 ms 31636 KB ok
16 Correct 12 ms 31704 KB ok
17 Correct 12 ms 31580 KB ok
18 Correct 13 ms 31580 KB ok
19 Correct 12 ms 31696 KB ok
20 Correct 12 ms 31580 KB ok
21 Correct 12 ms 31580 KB ok
22 Correct 11 ms 31628 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 12 ms 31684 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 12 ms 31732 KB ok
27 Correct 12 ms 31580 KB ok
28 Correct 12 ms 31580 KB ok
29 Correct 13 ms 31540 KB ok
30 Correct 12 ms 31836 KB ok
31 Correct 14 ms 31836 KB ok
32 Correct 12 ms 31576 KB ok
33 Correct 13 ms 31580 KB ok
34 Correct 13 ms 31576 KB ok
35 Correct 13 ms 31580 KB ok
36 Correct 11 ms 31616 KB ok
37 Correct 11 ms 31580 KB ok
38 Correct 11 ms 31580 KB ok
39 Correct 11 ms 31580 KB ok
40 Correct 12 ms 31580 KB ok
41 Correct 12 ms 31612 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31580 KB ok
2 Correct 12 ms 31580 KB ok
3 Correct 13 ms 31720 KB ok
4 Correct 11 ms 31580 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 16 ms 31576 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 12 ms 31624 KB ok
9 Correct 13 ms 31576 KB ok
10 Correct 13 ms 31576 KB ok
11 Correct 13 ms 31580 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 15 ms 31580 KB ok
14 Correct 12 ms 31580 KB ok
15 Correct 14 ms 31636 KB ok
16 Correct 12 ms 31704 KB ok
17 Correct 12 ms 31580 KB ok
18 Correct 13 ms 31580 KB ok
19 Correct 12 ms 31696 KB ok
20 Correct 12 ms 31580 KB ok
21 Correct 12 ms 31580 KB ok
22 Correct 11 ms 31628 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 12 ms 31684 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 12 ms 31732 KB ok
27 Correct 12 ms 31580 KB ok
28 Correct 12 ms 31580 KB ok
29 Correct 13 ms 31540 KB ok
30 Correct 12 ms 31836 KB ok
31 Correct 14 ms 31836 KB ok
32 Correct 12 ms 31576 KB ok
33 Correct 13 ms 31580 KB ok
34 Correct 13 ms 31576 KB ok
35 Correct 13 ms 31580 KB ok
36 Correct 11 ms 31616 KB ok
37 Correct 11 ms 31580 KB ok
38 Correct 11 ms 31580 KB ok
39 Correct 11 ms 31580 KB ok
40 Correct 12 ms 31580 KB ok
41 Correct 12 ms 31612 KB ok
42 Correct 436 ms 67924 KB ok
43 Correct 323 ms 61012 KB ok
44 Correct 595 ms 75600 KB ok
45 Correct 490 ms 70704 KB ok
46 Correct 546 ms 73780 KB ok
47 Correct 32 ms 37992 KB ok
48 Correct 107 ms 43600 KB ok
49 Correct 89 ms 42836 KB ok
50 Correct 215 ms 57524 KB ok
51 Correct 166 ms 48988 KB ok
52 Correct 50 ms 39508 KB ok
53 Correct 28 ms 37460 KB ok
54 Correct 52 ms 39760 KB ok
55 Correct 84 ms 41808 KB ok
56 Correct 41 ms 38992 KB ok
57 Correct 122 ms 50768 KB ok
58 Correct 159 ms 52048 KB ok
59 Correct 164 ms 53072 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31580 KB ok
2 Correct 12 ms 31580 KB ok
3 Correct 13 ms 31720 KB ok
4 Correct 11 ms 31580 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 12 ms 31748 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 13 ms 31836 KB ok
9 Correct 27 ms 37264 KB ok
10 Correct 224 ms 117040 KB ok
11 Correct 16 ms 31576 KB ok
12 Correct 12 ms 31580 KB ok
13 Correct 12 ms 31624 KB ok
14 Correct 13 ms 31576 KB ok
15 Correct 13 ms 31576 KB ok
16 Correct 13 ms 31580 KB ok
17 Correct 13 ms 31580 KB ok
18 Correct 15 ms 31580 KB ok
19 Correct 12 ms 31580 KB ok
20 Correct 14 ms 31636 KB ok
21 Correct 12 ms 31704 KB ok
22 Correct 12 ms 31580 KB ok
23 Correct 13 ms 31580 KB ok
24 Correct 12 ms 31696 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 12 ms 31580 KB ok
27 Correct 11 ms 31628 KB ok
28 Correct 12 ms 31580 KB ok
29 Correct 12 ms 31684 KB ok
30 Correct 12 ms 31580 KB ok
31 Correct 12 ms 31732 KB ok
32 Correct 12 ms 31580 KB ok
33 Correct 12 ms 31580 KB ok
34 Correct 13 ms 31540 KB ok
35 Correct 12 ms 31836 KB ok
36 Correct 14 ms 31836 KB ok
37 Correct 12 ms 31576 KB ok
38 Correct 13 ms 31580 KB ok
39 Correct 13 ms 31576 KB ok
40 Correct 13 ms 31580 KB ok
41 Correct 11 ms 31616 KB ok
42 Correct 11 ms 31580 KB ok
43 Correct 11 ms 31580 KB ok
44 Correct 11 ms 31580 KB ok
45 Correct 12 ms 31580 KB ok
46 Correct 12 ms 31612 KB ok
47 Correct 436 ms 67924 KB ok
48 Correct 323 ms 61012 KB ok
49 Correct 595 ms 75600 KB ok
50 Correct 490 ms 70704 KB ok
51 Correct 546 ms 73780 KB ok
52 Correct 32 ms 37992 KB ok
53 Correct 107 ms 43600 KB ok
54 Correct 89 ms 42836 KB ok
55 Correct 215 ms 57524 KB ok
56 Correct 166 ms 48988 KB ok
57 Correct 50 ms 39508 KB ok
58 Correct 28 ms 37460 KB ok
59 Correct 52 ms 39760 KB ok
60 Correct 84 ms 41808 KB ok
61 Correct 41 ms 38992 KB ok
62 Correct 122 ms 50768 KB ok
63 Correct 159 ms 52048 KB ok
64 Correct 164 ms 53072 KB ok
65 Execution timed out 4564 ms 415520 KB Time limit exceeded
66 Halted 0 ms 0 KB -