oj.uz

Submission #843889

# Submission time Handle Problem Language Result Execution time Memory
843889 2023-09-04T16:38:16 Z wii Soccer Stadium (IOI23_soccer) C++17
6 / 100
 472 ms 141932 KB 
// #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, 0, n + 1) foru(j, 0, n + 1) {
        ans[i][j] = 0;
        l[i][j] = 0;
        r[i][j] = 0;
        sum[i][j] = 0;
        nxt[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 temp[MaxN][MaxN];
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
    foru(i, 1, n) foru(j, 1, n) temp[i][j] = a[i][j];
    foru(i, 1, n) foru(j, 1, n) a[i][j] = temp[j][i];

    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 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 1 ms 12636 KB ok
5 Correct 2 ms 12636 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 5 ms 17244 KB ok
8 Correct 30 ms 44184 KB ok
9 Correct 472 ms 141932 KB ok

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 22.0

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

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 1 ms 12636 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 5 ms 17244 KB ok
9 Correct 30 ms 44184 KB ok
10 Correct 472 ms 141932 KB ok
11 Correct 1 ms 12632 KB ok
12 Correct 1 ms 12636 KB ok
13 Correct 1 ms 12636 KB ok
14 Correct 1 ms 12636 KB ok
15 Incorrect 1 ms 12636 KB wrong
16 Halted 0 ms 0 KB -