oj.uz

Submission #875087

# Submission time Handle Problem Language Result Execution time Memory
875087 2023-11-18T16:20:41 Z TheQuantiX Soccer Stadium (IOI23_soccer) C++17
6 / 100
 241 ms 39700 KB 
#include <bits/stdc++.h>
#include "soccer.h"

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
vector< vector<int> > f;
vector< vector<ll> > pref;

inline ll on_rectangle(ll u, ll l, ll d, ll r) {
    return pref[d + 1][r + 1] - pref[d + 1][l] - pref[u][r + 1] + pref[u][l];
}

inline int check(ll u, ll l, ll d, ll r) {
    // cout << u << ' ' << l << ' ' << d << ' ' << r << endl;
    int ans = 0;
    for (int lp = u; lp <= d; lp++) {
        for (int up = l; up <= r; up++) {
            if (on_rectangle(lp, l, lp, r) != 0) {
                continue;
            }
            if (on_rectangle(u, up, d, up) != 0) {
                continue;
            }
            // cout << '\t' << lp << ' ' << rp << ' ' << up << ' ' << dp << endl;
            // cout << '\t' << on_rectangle(u, l, lp - 1, up - 1) << ' ' << on_rectangle(u, up + 1, rp - 1, r) << ' ' << on_rectangle(lp + 1, l, d, dp - 1) << ' ' << on_rectangle(rp + 1, dp + 1, d, r) << ' ' << on_rectangle(u, l, d, r) << '\n';
            int cnt = (d - u + 1) * (r - l + 1);
            vector< vector<ll> > DP(d - u + 1, vector<ll>(r - l + 1, 1));
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp - 1; i >= u; i--) {
                for (int j = up - 1; j >= l; j--) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i + 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j + 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp - 1; i >= u; i--) {
                for (int j = up + 1; j <= r; j++) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i + 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j - 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp + 1; i <= d; i++) {
                for (int j = up - 1; j >= l; j--) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j + 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            for (int i = lp + 1; i <= d; i++) {
                for (int j = up + 1; j <= r; j++) {
                    // cout << "\t\tDEBUG" << endl;
                    if (f[i][j]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - 1 - u][j - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                    else if (!DP[i - u][j - 1 - l]) {
                        DP[i - u][j - l] = 0;
                        cnt--;
                    }
                }
            }
            // cout << "\t\tDEBUG" << endl;
            // cout << "\t" << cnt << endl;
            ans = max(ans, cnt);
        }
    }
    // cout << ans << endl;
    return ans;
}

int solve1(vector< vector<int> > F) {
    f = F;
    pref.resize(n + 1);
    for (int i = 0; i < n + 1; i++) {
        pref[i].resize(n + 1);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + F[i][j];
        }
    }
    int ans = 0;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = i1; i2 < n; i2++) {
            for (int j1 = 0; j1 < n; j1++) {
                for (int j2 = j1; j2 < n; j2++) {
                    ans = max(ans, check(i1, j1, i2, j2));
                }
            }
        }
    }
    return ans;
}

int biggest_stadium(int N, vector< vector<int> > F) {
    n = N;
    if (n <= 7) {
        return solve1(F);
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (F[i][j] == 1) {
                return n * n - min(min((i + 1) * (j + 1), (n - i) * (j + 1)), min((i + 1) * (n - j), (n - i) * (n - j)));
            }
        }
    }
    return n * n;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 16 ms 2692 KB ok
9 Correct 241 ms 39700 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Incorrect 0 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Incorrect 0 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Incorrect 0 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Incorrect 0 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 16 ms 2692 KB ok
10 Correct 241 ms 39700 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Incorrect 0 ms 348 KB wrong
16 Halted 0 ms 0 KB -