oj.uz

Submission #916632

# Submission time Handle Problem Language Result Execution time Memory
916632 2024-01-26T07:57:35 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4474 ms 487528 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=32,inf=1e9;
int n,ans,dp[2][mxn][mxn][mxn][mxn][mxn][2];
vector <vector <int>> s;
int sum(int i, int l, int r){
    return s[i][r]-s[i][l-1];
}
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    s.resize(N+2);
    for (int i=0;i<N+2;i++){
        s[i].assign(N+2,0);
        if (i&&i<N+1)
            for (int j=1;j<=N;j++)
                s[i][j]=s[i][j-1]+F[i-1][j-1];
    }
    for (int i=1;i<=N;i++){
        int cur=-1;
        for (int j=0;j<N;j++){
            if (F[i-1][j])
                cur=j;
            ans=max(ans,j-cur);
        }
    }
    for (int i=0;i<=N;i++){
        for (int j=N+1;j>i;j--)
            for (int l=N;l;l--)
                for (int r=1;r<=N;r++)
                    for (int u=N;u;u--)
                        for (int v=u;v<=N;v++)
                            for (int b=1;b>=0;b--){
                                if (l>r||u>v||!((l>=u&&r<=v)||(l<=u&&r>=v))){
                                    dp[i&1][j][l][r][u][v][b]=-inf;
                                    continue;
                                }
                                int res=0,x=(r-l+1>v-u+1?i:j);
                                if (!b)
                                    res=dp[i&1][j][l][r][u][v][1];
                                if (b)
                                    x=i^j^x;
                                if (x==i){
                                    if (i){
                                        res=max(res,max(dp[i&1][j][l+1][r][u][v][b],dp[i&1][j][l][r-1][u][v][b]));
                                        if (!sum(i,l,r))
                                            res=max(res,dp[(i&1)^1][j][l][r][u][v][b]+r-l+1);
                                    }
                                }
                                else if (j<=n){
                                    res=max(res,max(dp[i&1][j][l][r][u+1][v][b],dp[i&1][j][l][r][u][v-1][b]));
                                    if (!sum(j,u,v))
                                        res=max(res,dp[i&1][j+1][l][r][u][v][b]+v-u+1);
                                }
                                dp[i&1][j][l][r][u][v][b]=res;
                                if (i<N&&j==i+1&&l==1&&r==N&&u==1&&v==N&&!b)
                                    ans=max(ans,res);
                            }

    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 3 ms 14692 KB ok
3 Correct 21 ms 78172 KB ok
4 Correct 23 ms 86364 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 2 ms 14684 KB ok
7 Runtime error 13 ms 604 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 3 ms 14692 KB ok
3 Correct 3 ms 14936 KB ok
4 Correct 3 ms 14684 KB ok
5 Correct 3 ms 14684 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 3 ms 14684 KB ok
8 Correct 3 ms 14684 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 3 ms 14680 KB ok
11 Correct 3 ms 14684 KB ok
12 Correct 2 ms 14684 KB ok
13 Correct 2 ms 14684 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22884 KB ok
2 Correct 3 ms 14684 KB ok
3 Correct 3 ms 14692 KB ok
4 Correct 3 ms 14936 KB ok
5 Correct 3 ms 14684 KB ok
6 Correct 3 ms 14684 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 3 ms 14684 KB ok
9 Correct 3 ms 14684 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 3 ms 14680 KB ok
12 Correct 3 ms 14684 KB ok
13 Correct 2 ms 14684 KB ok
14 Correct 2 ms 14684 KB ok
15 Correct 6 ms 31068 KB ok
16 Correct 7 ms 31068 KB ok
17 Correct 6 ms 31068 KB ok
18 Correct 6 ms 31064 KB ok
19 Correct 7 ms 31216 KB ok
20 Correct 7 ms 31068 KB ok
21 Correct 6 ms 31196 KB ok
22 Correct 5 ms 31068 KB ok
23 Correct 6 ms 31068 KB ok
24 Correct 6 ms 31068 KB ok
25 Correct 7 ms 31068 KB ok
26 Correct 6 ms 31068 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22884 KB ok
2 Correct 3 ms 14684 KB ok
3 Correct 3 ms 14692 KB ok
4 Correct 21 ms 78172 KB ok
5 Correct 23 ms 86364 KB ok
6 Correct 3 ms 14936 KB ok
7 Correct 3 ms 14684 KB ok
8 Correct 3 ms 14684 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 3 ms 14684 KB ok
11 Correct 3 ms 14684 KB ok
12 Correct 2 ms 14684 KB ok
13 Correct 3 ms 14680 KB ok
14 Correct 3 ms 14684 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14684 KB ok
17 Correct 6 ms 31068 KB ok
18 Correct 7 ms 31068 KB ok
19 Correct 6 ms 31068 KB ok
20 Correct 6 ms 31064 KB ok
21 Correct 7 ms 31216 KB ok
22 Correct 7 ms 31068 KB ok
23 Correct 6 ms 31196 KB ok
24 Correct 5 ms 31068 KB ok
25 Correct 6 ms 31068 KB ok
26 Correct 6 ms 31068 KB ok
27 Correct 7 ms 31068 KB ok
28 Correct 6 ms 31068 KB ok
29 Correct 6 ms 31064 KB ok
30 Correct 4184 ms 476352 KB ok
31 Correct 3863 ms 476424 KB ok
32 Correct 3638 ms 475916 KB ok
33 Correct 3663 ms 476016 KB ok
34 Correct 3687 ms 483672 KB ok
35 Correct 3729 ms 487356 KB ok
36 Correct 3595 ms 487528 KB ok
37 Correct 3682 ms 487172 KB ok
38 Correct 3761 ms 486580 KB ok
39 Correct 3580 ms 487228 KB ok
40 Correct 4474 ms 487160 KB ok
41 Correct 4339 ms 487160 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22884 KB ok
2 Correct 3 ms 14684 KB ok
3 Correct 3 ms 14692 KB ok
4 Correct 21 ms 78172 KB ok
5 Correct 23 ms 86364 KB ok
6 Correct 3 ms 14936 KB ok
7 Correct 3 ms 14684 KB ok
8 Correct 3 ms 14684 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 3 ms 14684 KB ok
11 Correct 3 ms 14684 KB ok
12 Correct 2 ms 14684 KB ok
13 Correct 3 ms 14680 KB ok
14 Correct 3 ms 14684 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14684 KB ok
17 Correct 6 ms 31068 KB ok
18 Correct 7 ms 31068 KB ok
19 Correct 6 ms 31068 KB ok
20 Correct 6 ms 31064 KB ok
21 Correct 7 ms 31216 KB ok
22 Correct 7 ms 31068 KB ok
23 Correct 6 ms 31196 KB ok
24 Correct 5 ms 31068 KB ok
25 Correct 6 ms 31068 KB ok
26 Correct 6 ms 31068 KB ok
27 Correct 7 ms 31068 KB ok
28 Correct 6 ms 31068 KB ok
29 Correct 6 ms 31064 KB ok
30 Correct 4184 ms 476352 KB ok
31 Correct 3863 ms 476424 KB ok
32 Correct 3638 ms 475916 KB ok
33 Correct 3663 ms 476016 KB ok
34 Correct 3687 ms 483672 KB ok
35 Correct 3729 ms 487356 KB ok
36 Correct 3595 ms 487528 KB ok
37 Correct 3682 ms 487172 KB ok
38 Correct 3761 ms 486580 KB ok
39 Correct 3580 ms 487228 KB ok
40 Correct 4474 ms 487160 KB ok
41 Correct 4339 ms 487160 KB ok
42 Runtime error 28 ms 4176 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22884 KB ok
2 Correct 3 ms 14684 KB ok
3 Correct 3 ms 14692 KB ok
4 Correct 21 ms 78172 KB ok
5 Correct 23 ms 86364 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 2 ms 14684 KB ok
8 Runtime error 13 ms 604 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -