Submission #843885

#	Time	Username	Problem	Language	Result	Execution time	Memory
843885		wii	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	378 ms	132992 KiB

soccer

// #define testing

#ifdef testing
    #include <cassert>
    #include <cstdio>
    #include <vector>
    #include <iostream>
#else
    #include "soccer.h"
#endif //testing

using namespace std;

#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
const int MaxN = 2e3 + 5;

int n;
int a[MaxN][MaxN];
int l[MaxN][MaxN], r[MaxN][MaxN], sum[MaxN][MaxN], nxt[MaxN][MaxN], ans[MaxN][MaxN];

int get(int u, int v, int val, int arr[MaxN][MaxN]) {
    int &x = nxt[u][v];
    return arr[x][v] > val ? x = get(x, v, val, arr) : x;
}

int sol() {
    int res = 0;
    foru(i, 1, n) foru(j, 1, n) ans[i][j] = 0;

    foru(i, 1, n) {
        foru(j, 1, n) l[i][j] = (a[i][j] ? 0 : l[i][j - 1] + 1);
        ford(j, n, 1) r[i][j] = (a[i][j] ? 0 : r[i][j + 1] + 1);
    }

    foru(i, 1, n) {
        foru(j, 1, n) if (a[i][j] == 0) {
            sum[i][j] = 0;
            nxt[i][j] = i - 1;
            int prv = get(i, j, l[i][j], l);

            sum[i][j] = sum[prv][j] + l[i][j] * (i - prv);
            ans[i][j] += sum[i][j];
        }
    }

    foru(i, 1, n) {
        foru(j, 1, n) if (a[i][j] == 0) {
            sum[i][j] = 0;
            nxt[i][j] = i - 1;
            int prv = get(i, j, r[i][j], r);

            sum[i][j] = sum[prv][j] + r[i][j] * (i - prv);
            ans[i][j] += sum[i][j];
        }
    }

    ford(i, n, 1) {
        foru(j, 1, n) if (a[i][j] == 0) {
            sum[i][j] = 0;
            nxt[i][j] = i + 1;
            int prv = get(i, j, l[i][j], l);

            sum[i][j] = sum[prv][j] + l[i][j] * -(i - prv);
            ans[i][j] += sum[i][j];
        }
    }

    ford(i, n, 1) {
        foru(j, 1, n) if (a[i][j] == 0) {
            sum[i][j] = 0;
            nxt[i][j] = i + 1;
            int prv = get(i, j, r[i][j], r);

            sum[i][j] = sum[prv][j] + r[i][j] * -(i - prv);
            ans[i][j] += sum[i][j];
        }
    }

    foru(i, 1, n) foru(j, 1, n)
        sum[i][j] = (a[i][j] ? 0 : sum[i - 1][j] + 1), ans[i][j] -= sum[i][j];
    
    ford(i, n, 1) foru(j, 1, n)
        sum[i][j] = (a[i][j] ? 0 : sum[i + 1][j] + 1), ans[i][j] -= sum[i][j];

    foru(i, 1, n) foru(j, 1, n) if (a[i][j] == 0) ans[i][j] -= l[i][j] + r[i][j];

    foru(i, 1, n) foru(j, 1, n) if (a[i][j] == 0)
        res = max(res, ans[i][j] + 1);

    return res;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n = N;
    foru(i, 0, n + 1) foru(j, 0, n + 1) a[i][j] = 1;

    foru(i, 1, n) foru(j, 1, n)
        a[i][j] = F[i - 1][j - 1];

    int ans = 0;

    ans = max(ans, sol());
    // rotation
    // ans = max(ans, sol());

    return ans;
}

#ifdef testing
int main()
{
    if (fopen("01.in", "r")) {
        freopen("01.in", "r", stdin);
        freopen("01.out", "w", stdout);
    }

    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30