oj.uz

답안 #843928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843928 2023-09-04T17:12:14 Z wii 축구 경기장 (IOI23_soccer) C++17
6 / 100
 475 ms 141844 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, 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) ans[i][j] = 0;
    foru(i, 0, n + 1) foru(j, 0, n + 1) sum[i][j] = 0; 
    foru(i, 1, n) {
        foru(j, 1, n) if (a[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, 0, n + 1) foru(j, 0, n + 1) sum[i][j] = 0; 
    ford(i, n, 1) {
        foru(j, 1, n) if (a[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)
        ans[i][j] -= l[i][j];

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

    foru(i, 1, n) foru(j, 1, n) ans[i][j] = 0;
    foru(i, 0, n + 1) foru(j, 0, n + 1) sum[i][j] = 0; 
    foru(i, 1, n) {
        foru(j, 1, n) if (a[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, 0, n + 1) foru(j, 0, n + 1) sum[i][j] = 0; 
    ford(i, n, 1) {
        foru(j, 1, n) if (a[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)
        ans[i][j] -= r[i][j];

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

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 8536 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 3 ms 11864 KB ok
8 Correct 34 ms 38748 KB ok
9 Correct 475 ms 141844 KB ok

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 10588 KB ok
7 Partially correct 1 ms 10584 KB partial
8 Correct 1 ms 10704 KB ok
9 Correct 2 ms 8628 KB ok
10 Correct 1 ms 8536 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 2 ms 10676 KB ok
13 Incorrect 1 ms 12632 KB wrong
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 1 ms 10588 KB ok
8 Partially correct 1 ms 10584 KB partial
9 Correct 1 ms 10704 KB ok
10 Correct 2 ms 8628 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 2 ms 10676 KB ok
14 Incorrect 1 ms 12632 KB wrong
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 10584 KB ok
9 Correct 1 ms 10588 KB ok
10 Partially correct 1 ms 10584 KB partial
11 Correct 1 ms 10704 KB ok
12 Correct 2 ms 8628 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 2 ms 10676 KB ok
16 Incorrect 1 ms 12632 KB wrong
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 10584 KB ok
9 Correct 1 ms 10588 KB ok
10 Partially correct 1 ms 10584 KB partial
11 Correct 1 ms 10704 KB ok
12 Correct 2 ms 8628 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 2 ms 10676 KB ok
16 Incorrect 1 ms 12632 KB wrong
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 3 ms 11864 KB ok
9 Correct 34 ms 38748 KB ok
10 Correct 475 ms 141844 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 10584 KB ok
14 Correct 1 ms 10588 KB ok
15 Partially correct 1 ms 10584 KB partial
16 Correct 1 ms 10704 KB ok
17 Correct 2 ms 8628 KB ok
18 Correct 1 ms 8536 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 2 ms 10676 KB ok
21 Incorrect 1 ms 12632 KB wrong
22 Halted 0 ms 0 KB -