oj.uz

답안 #1059783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1059783 2024-08-15T08:10:33 Z aykhn 축구 경기장 (IOI23_soccer) C++17
54 / 100
 206 ms 47392 KB 
#include <bits/stdc++.h>
#include "soccer.h"
 
using namespace std;
 
int n;
vector<vector<int>> A;
int dp[31][31][31][31];
int cur;
 
int f(int i, int pos, int l, int r)
{
    if (i < 0 || i >= n) return 0;
    if (l > r) return 0;
    if (pos >= n) return 0;
    if (dp[i][pos][l][r] != -1) return dp[i][pos][l][r];
    vector<int> v;
    v.push_back(l - 1);
    for (int j = l; j <= r; j++) if (A[i][j]) v.push_back(j);
    v.push_back(r + 1);
    int res = 0;
    for (int j = 1; j < v.size(); j++)
    {
        if (i <= cur) 
        {
            res = max(res, f(i - 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
            res = max(res, f(cur + (pos - (cur - i)) + 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
        }
        else
        {
            res = max(res, f(i + 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
            res = max(res, f(cur - (pos - (i - cur)) - 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
        }
    }
    return dp[i][pos][l][r] = res;
}
 
int solve()
{
    for (int i = 0; i < 31; i++)
    {
        for (int j = 0; j < 31; j++)
        {
            for (int k = 0; k < 31; k++)
            {
                for (int l = k; l < 31; l++) dp[i][j][k][l] = -1;
            }
        }
    }
    return f(cur, 0, 0, n - 1);
}
 
int calc(int i, int j)
{
    return i * n + j * n - i * j;
}
 
int biggest_stadium(int N, vector<vector<int>> B)
{
    n = N;
    A = B;
    int c = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            c += A[i][j];
        }
    }
    if (c == 1)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (A[i][j])
                {
                    int i1 = n - i - 1, j1 = n - j - 1;
                    return max({calc(i, j), calc(i1, j), calc(i, j1), calc(i1, j1)});
                }
            }
        }
    }
    int ok = 1, c1 = 0;
    int l[N], r[N], cnt[N];
    array<int, 2> mx = {-1, -1};
    for (int i = 0; i < n; i++)
    {
        cnt[i] = 0;
        l[i] = n + 1, r[i] = -1;
        for (int j = 0; j < n; j++)
        {
            if (A[i][j]) continue;
            cnt[i]++,
            l[i] = min(l[i], j), r[i] = max(r[i], j);
        }
        if (!cnt[i]) continue;
        if (cnt[i] != r[i] - l[i] + 1) ok = 0;
        c1++;
        mx = max(mx, {cnt[i], i});
    }
    if (N > 30)
    {
        int lx = mx[1] - 1, rx = mx[1] + 1;
        int last = mx[1];
        while (lx >= 0 || rx < N)
        {
            if (lx >= 0 && cnt[lx] && (rx == N || cnt[lx] <= cnt[rx]))
            {
                if (!(l[last] <= l[lx] && r[lx] <= r[last])) 
                {
                    ok = 0;
                    break;
                }
                last = lx;
                lx--;
            }
            else if (rx < N && cnt[rx] && (lx == -1 || cnt[rx] <= cnt[lx]))
            {
                if (!(l[last] <= l[rx] && r[rx] <= r[last])) 
                {
                    ok = 0;
                    break;
                }
                last = rx;
                rx++;
            }
            else break;
        }
        if (rx - lx - 1 == c1 && ok)
        {
            return n * n - c;
        }
        return 0;
    }
    int res = 0;
    for (cur = 0; cur < n; cur++)
    {
        res = max(res, solve());
    }
    return res;
}

Compilation message

soccer.cpp: In function 'int f(int, int, int, int)':
soccer.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int j = 1; j < v.size(); j++)
      |                     ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 12 ms 3236 KB ok
9 Correct 206 ms 47392 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 2 ms 3928 KB ok
4 Correct 2 ms 3928 KB ok
5 Correct 2 ms 3932 KB ok
6 Correct 2 ms 4052 KB ok
7 Correct 2 ms 3932 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 2 ms 3932 KB ok
10 Correct 2 ms 3932 KB ok
11 Correct 2 ms 3932 KB ok
12 Correct 2 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3932 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 2 ms 3928 KB ok
5 Correct 2 ms 3928 KB ok
6 Correct 2 ms 3932 KB ok
7 Correct 2 ms 4052 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 2 ms 3932 KB ok
10 Correct 2 ms 3932 KB ok
11 Correct 2 ms 3932 KB ok
12 Correct 2 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 2 ms 3932 KB ok
15 Correct 4 ms 3932 KB ok
16 Correct 3 ms 3932 KB ok
17 Correct 3 ms 3932 KB ok
18 Correct 3 ms 3932 KB ok
19 Correct 4 ms 3932 KB ok
20 Correct 3 ms 3932 KB ok
21 Correct 4 ms 4048 KB ok
22 Correct 3 ms 4044 KB ok
23 Correct 4 ms 3928 KB ok
24 Correct 3 ms 3928 KB ok
25 Correct 4 ms 3928 KB ok
26 Correct 4 ms 3932 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3932 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 2 ms 3928 KB ok
7 Correct 2 ms 3928 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 2 ms 4052 KB ok
10 Correct 2 ms 3932 KB ok
11 Correct 2 ms 3932 KB ok
12 Correct 2 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 2 ms 3932 KB ok
15 Correct 2 ms 3932 KB ok
16 Correct 2 ms 3932 KB ok
17 Correct 4 ms 3932 KB ok
18 Correct 3 ms 3932 KB ok
19 Correct 3 ms 3932 KB ok
20 Correct 3 ms 3932 KB ok
21 Correct 4 ms 3932 KB ok
22 Correct 3 ms 3932 KB ok
23 Correct 4 ms 4048 KB ok
24 Correct 3 ms 4044 KB ok
25 Correct 4 ms 3928 KB ok
26 Correct 3 ms 3928 KB ok
27 Correct 4 ms 3928 KB ok
28 Correct 4 ms 3932 KB ok
29 Correct 4 ms 3928 KB ok
30 Correct 12 ms 4064 KB ok
31 Correct 11 ms 3932 KB ok
32 Correct 11 ms 3932 KB ok
33 Correct 10 ms 3932 KB ok
34 Correct 11 ms 3928 KB ok
35 Correct 10 ms 3932 KB ok
36 Correct 11 ms 3932 KB ok
37 Correct 11 ms 3932 KB ok
38 Correct 10 ms 4056 KB ok
39 Correct 10 ms 3932 KB ok
40 Correct 11 ms 4056 KB ok
41 Correct 12 ms 4060 KB ok

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3932 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 2 ms 3928 KB ok
7 Correct 2 ms 3928 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 2 ms 4052 KB ok
10 Correct 2 ms 3932 KB ok
11 Correct 2 ms 3932 KB ok
12 Correct 2 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 2 ms 3932 KB ok
15 Correct 2 ms 3932 KB ok
16 Correct 2 ms 3932 KB ok
17 Correct 4 ms 3932 KB ok
18 Correct 3 ms 3932 KB ok
19 Correct 3 ms 3932 KB ok
20 Correct 3 ms 3932 KB ok
21 Correct 4 ms 3932 KB ok
22 Correct 3 ms 3932 KB ok
23 Correct 4 ms 4048 KB ok
24 Correct 3 ms 4044 KB ok
25 Correct 4 ms 3928 KB ok
26 Correct 3 ms 3928 KB ok
27 Correct 4 ms 3928 KB ok
28 Correct 4 ms 3932 KB ok
29 Correct 4 ms 3928 KB ok
30 Correct 12 ms 4064 KB ok
31 Correct 11 ms 3932 KB ok
32 Correct 11 ms 3932 KB ok
33 Correct 10 ms 3932 KB ok
34 Correct 11 ms 3928 KB ok
35 Correct 10 ms 3932 KB ok
36 Correct 11 ms 3932 KB ok
37 Correct 11 ms 3932 KB ok
38 Correct 10 ms 4056 KB ok
39 Correct 10 ms 3932 KB ok
40 Correct 11 ms 4056 KB ok
41 Correct 12 ms 4060 KB ok
42 Partially correct 14 ms 3296 KB partial
43 Partially correct 14 ms 3268 KB partial
44 Partially correct 14 ms 3416 KB partial
45 Partially correct 13 ms 3420 KB partial
46 Partially correct 13 ms 3420 KB partial
47 Partially correct 14 ms 3420 KB partial
48 Incorrect 13 ms 3420 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3932 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 3932 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 12 ms 3236 KB ok
10 Correct 206 ms 47392 KB ok
11 Correct 2 ms 3928 KB ok
12 Correct 2 ms 3928 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 2 ms 4052 KB ok
15 Correct 2 ms 3932 KB ok
16 Correct 2 ms 3932 KB ok
17 Correct 2 ms 3932 KB ok
18 Correct 2 ms 3932 KB ok
19 Correct 2 ms 3932 KB ok
20 Correct 2 ms 3932 KB ok
21 Correct 2 ms 3932 KB ok
22 Correct 4 ms 3932 KB ok
23 Correct 3 ms 3932 KB ok
24 Correct 3 ms 3932 KB ok
25 Correct 3 ms 3932 KB ok
26 Correct 4 ms 3932 KB ok
27 Correct 3 ms 3932 KB ok
28 Correct 4 ms 4048 KB ok
29 Correct 3 ms 4044 KB ok
30 Correct 4 ms 3928 KB ok
31 Correct 3 ms 3928 KB ok
32 Correct 4 ms 3928 KB ok
33 Correct 4 ms 3932 KB ok
34 Correct 4 ms 3928 KB ok
35 Correct 12 ms 4064 KB ok
36 Correct 11 ms 3932 KB ok
37 Correct 11 ms 3932 KB ok
38 Correct 10 ms 3932 KB ok
39 Correct 11 ms 3928 KB ok
40 Correct 10 ms 3932 KB ok
41 Correct 11 ms 3932 KB ok
42 Correct 11 ms 3932 KB ok
43 Correct 10 ms 4056 KB ok
44 Correct 10 ms 3932 KB ok
45 Correct 11 ms 4056 KB ok
46 Correct 12 ms 4060 KB ok
47 Partially correct 14 ms 3296 KB partial
48 Partially correct 14 ms 3268 KB partial
49 Partially correct 14 ms 3416 KB partial
50 Partially correct 13 ms 3420 KB partial
51 Partially correct 13 ms 3420 KB partial
52 Partially correct 14 ms 3420 KB partial
53 Incorrect 13 ms 3420 KB wrong
54 Halted 0 ms 0 KB -