oj.uz

Submission #1011926

# Submission time Handle Problem Language Result Execution time Memory
1011926 2024-07-01T11:13:17 Z mdn2002 Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 574236 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]);
                ans = max(ans, f(j, z, x - 1, y) + z - j + 1);
                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 12 ms 31576 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31512 KB ok
2 Correct 12 ms 31580 KB ok
3 Correct 13 ms 31580 KB ok
4 Correct 12 ms 31580 KB ok
5 Correct 12 ms 31700 KB ok
6 Correct 12 ms 31832 KB ok
7 Correct 13 ms 31836 KB ok
8 Correct 27 ms 36692 KB ok
9 Correct 219 ms 118692 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31512 KB ok
2 Correct 12 ms 31580 KB ok
3 Correct 12 ms 31580 KB ok
4 Correct 13 ms 31580 KB ok
5 Correct 12 ms 31724 KB ok
6 Correct 12 ms 31624 KB ok
7 Correct 12 ms 31580 KB ok
8 Correct 13 ms 31580 KB ok
9 Correct 13 ms 31580 KB ok
10 Correct 13 ms 31712 KB ok
11 Correct 13 ms 31580 KB ok
12 Correct 12 ms 31580 KB ok
13 Correct 15 ms 31656 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 13 ms 31512 KB ok
3 Correct 12 ms 31580 KB ok
4 Correct 12 ms 31580 KB ok
5 Correct 13 ms 31580 KB ok
6 Correct 12 ms 31724 KB ok
7 Correct 12 ms 31624 KB ok
8 Correct 12 ms 31580 KB ok
9 Correct 13 ms 31580 KB ok
10 Correct 13 ms 31580 KB ok
11 Correct 13 ms 31712 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 12 ms 31580 KB ok
14 Correct 15 ms 31656 KB ok
15 Correct 13 ms 31580 KB ok
16 Correct 12 ms 31580 KB ok
17 Correct 12 ms 31608 KB ok
18 Correct 13 ms 31580 KB ok
19 Correct 11 ms 31580 KB ok
20 Correct 12 ms 31632 KB ok
21 Correct 12 ms 31572 KB ok
22 Correct 12 ms 31580 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 12 ms 31580 KB ok
25 Correct 13 ms 31580 KB ok
26 Correct 12 ms 31596 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 13 ms 31512 KB ok
3 Correct 12 ms 31580 KB ok
4 Correct 13 ms 31580 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 13 ms 31580 KB ok
8 Correct 12 ms 31724 KB ok
9 Correct 12 ms 31624 KB ok
10 Correct 12 ms 31580 KB ok
11 Correct 13 ms 31580 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 13 ms 31712 KB ok
14 Correct 13 ms 31580 KB ok
15 Correct 12 ms 31580 KB ok
16 Correct 15 ms 31656 KB ok
17 Correct 13 ms 31580 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 12 ms 31608 KB ok
20 Correct 13 ms 31580 KB ok
21 Correct 11 ms 31580 KB ok
22 Correct 12 ms 31632 KB ok
23 Correct 12 ms 31572 KB ok
24 Correct 12 ms 31580 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 12 ms 31580 KB ok
27 Correct 13 ms 31580 KB ok
28 Correct 12 ms 31596 KB ok
29 Correct 13 ms 31580 KB ok
30 Correct 13 ms 31836 KB ok
31 Correct 14 ms 31868 KB ok
32 Correct 12 ms 31576 KB ok
33 Correct 13 ms 31716 KB ok
34 Correct 12 ms 31580 KB ok
35 Correct 12 ms 31580 KB ok
36 Correct 12 ms 31612 KB ok
37 Correct 13 ms 31856 KB ok
38 Correct 13 ms 31576 KB ok
39 Correct 14 ms 31580 KB ok
40 Correct 13 ms 31576 KB ok
41 Correct 12 ms 31576 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 13 ms 31512 KB ok
3 Correct 12 ms 31580 KB ok
4 Correct 13 ms 31580 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 12 ms 31580 KB ok
7 Correct 13 ms 31580 KB ok
8 Correct 12 ms 31724 KB ok
9 Correct 12 ms 31624 KB ok
10 Correct 12 ms 31580 KB ok
11 Correct 13 ms 31580 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 13 ms 31712 KB ok
14 Correct 13 ms 31580 KB ok
15 Correct 12 ms 31580 KB ok
16 Correct 15 ms 31656 KB ok
17 Correct 13 ms 31580 KB ok
18 Correct 12 ms 31580 KB ok
19 Correct 12 ms 31608 KB ok
20 Correct 13 ms 31580 KB ok
21 Correct 11 ms 31580 KB ok
22 Correct 12 ms 31632 KB ok
23 Correct 12 ms 31572 KB ok
24 Correct 12 ms 31580 KB ok
25 Correct 12 ms 31580 KB ok
26 Correct 12 ms 31580 KB ok
27 Correct 13 ms 31580 KB ok
28 Correct 12 ms 31596 KB ok
29 Correct 13 ms 31580 KB ok
30 Correct 13 ms 31836 KB ok
31 Correct 14 ms 31868 KB ok
32 Correct 12 ms 31576 KB ok
33 Correct 13 ms 31716 KB ok
34 Correct 12 ms 31580 KB ok
35 Correct 12 ms 31580 KB ok
36 Correct 12 ms 31612 KB ok
37 Correct 13 ms 31856 KB ok
38 Correct 13 ms 31576 KB ok
39 Correct 14 ms 31580 KB ok
40 Correct 13 ms 31576 KB ok
41 Correct 12 ms 31576 KB ok
42 Correct 1012 ms 126564 KB ok
43 Correct 515 ms 78928 KB ok
44 Execution timed out 4601 ms 574236 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB ok
2 Correct 13 ms 31512 KB ok
3 Correct 12 ms 31580 KB ok
4 Correct 13 ms 31580 KB ok
5 Correct 12 ms 31580 KB ok
6 Correct 12 ms 31700 KB ok
7 Correct 12 ms 31832 KB ok
8 Correct 13 ms 31836 KB ok
9 Correct 27 ms 36692 KB ok
10 Correct 219 ms 118692 KB ok
11 Correct 12 ms 31580 KB ok
12 Correct 13 ms 31580 KB ok
13 Correct 12 ms 31724 KB ok
14 Correct 12 ms 31624 KB ok
15 Correct 12 ms 31580 KB ok
16 Correct 13 ms 31580 KB ok
17 Correct 13 ms 31580 KB ok
18 Correct 13 ms 31712 KB ok
19 Correct 13 ms 31580 KB ok
20 Correct 12 ms 31580 KB ok
21 Correct 15 ms 31656 KB ok
22 Correct 13 ms 31580 KB ok
23 Correct 12 ms 31580 KB ok
24 Correct 12 ms 31608 KB ok
25 Correct 13 ms 31580 KB ok
26 Correct 11 ms 31580 KB ok
27 Correct 12 ms 31632 KB ok
28 Correct 12 ms 31572 KB ok
29 Correct 12 ms 31580 KB ok
30 Correct 12 ms 31580 KB ok
31 Correct 12 ms 31580 KB ok
32 Correct 13 ms 31580 KB ok
33 Correct 12 ms 31596 KB ok
34 Correct 13 ms 31580 KB ok
35 Correct 13 ms 31836 KB ok
36 Correct 14 ms 31868 KB ok
37 Correct 12 ms 31576 KB ok
38 Correct 13 ms 31716 KB ok
39 Correct 12 ms 31580 KB ok
40 Correct 12 ms 31580 KB ok
41 Correct 12 ms 31612 KB ok
42 Correct 13 ms 31856 KB ok
43 Correct 13 ms 31576 KB ok
44 Correct 14 ms 31580 KB ok
45 Correct 13 ms 31576 KB ok
46 Correct 12 ms 31576 KB ok
47 Correct 1012 ms 126564 KB ok
48 Correct 515 ms 78928 KB ok
49 Execution timed out 4601 ms 574236 KB Time limit exceeded
50 Halted 0 ms 0 KB -