oj.uz

Submission #1018105

# Submission time Handle Problem Language Result Execution time Memory
1018105 2024-07-09T14:25:11 Z kym Soccer Stadium (IOI23_soccer) C++17
48 / 100
 19 ms 12528 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int oo=1'000'000'000ll;
int check(int n, vector<vector<int>> F)
{
    int tot=0;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)tot+=F[i][j]==0;
    for(int j=0;j<n;j++){ // this checks every column fulfill the condition
        int stage=0;
        for(int i=0;i<n;i++){
            if(stage==0){
                if(F[i][j]==1)continue;
                else stage=1;
            } else if(stage==1){
                if(F[i][j]==1)stage=2;
                else continue;
            } else if(stage==2){
                if(F[i][j]==1)continue;
                else return 0;
            }
        }
    }
    for(int i=0;i<n;i++){
        int stage=0;
        for(int j=0;j<n;j++){
            if(stage==0){
                if(F[i][j]==1)continue;
                else stage=1;
            } else if(stage==1){
                if(F[i][j]==1)stage=2;
                else continue;
            } else if(stage==2){
                if(F[i][j]==1)continue;
                else return 0;
            }
        }
    }
    vector<int> F1(n,oo);
    vector<int> L0(n,-1);
    for(int j=0;j<n;j++){
        for(int i=0;i<n;i++){
            if(F[i][j] == 0){
                L0[j]=i;
            } else{
                F1[j]=min(F1[j],i);
            }
        }
    }
 
    for(int i=0;i<n;i++){
        vector<int> vec;
        for(int j=0;j<n;j++)if(F[i][j]==0){
            vec.push_back(j);
        }
        if(vec.empty())continue;
        int st=vec[0], en=vec.back();
        int worst=oo;
        for(int i=st;i<=en;i++){
            worst=min(worst,L0[i]);
        }
        int best=0;
        for(int i=0;i<st;i++){
            best=max(best,L0[i]);
        }
        for(int i=en+1;i<n;i++){
            best=max(best,L0[i]);
        }
        if(best>worst){
            return 0;
        }
    }
    return tot;
}
const int MAXN=31;
int dp[MAXN][MAXN][MAXN][MAXN];
int biggest_stadium(int n, vector<vector<int>> F)
{
    int can=check(n,F);
    int ans=0;
    if(can)return can;
    for(int i=0;i<MAXN;i++)for(int j=0;j<MAXN;j++)for(int k=0;k<MAXN;k++)for(int z=0;z<MAXN;z++)dp[i][j][k][z]=-oo;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=j;k<n;k++){
                if(F[i][k]==1)break;
                dp[i][i][j][k]=k-j+1;
                ans=max(ans,k-j+1);
            }
        }
    }

    for(int i=n-1;i>=0;i--){
        for(int j=i;j<=n-1;j++){
            for(int x=0;x<n;x++){
                for(int y=x;y<n;y++){
                    if(dp[i][j][x][y] == -oo)continue;//no way bro
                    ans=max(ans,dp[i][j][x][y]);
                    if(i!=0){ // try putting a thing at i-1
                        for(int nx=x;nx<=y;nx++){
                            for(int ny=nx;ny<=y;ny++){
                                if(F[i-1][ny] == 1)break; // cannot 
                                dp[i-1][j][nx][ny]=max(dp[i-1][j][nx][ny],dp[i][j][x][y]+(ny-nx+1));
                                ans=max(ans,dp[i-1][j][nx][ny]);
                            }
                        }
                    }
                    if(j!=n-1){
                        for(int nx=x;nx<=y;nx++){
                            for(int ny=nx;ny<=y;ny++){
                                if(F[j+1][ny] == 1)break; // cannot 
                                dp[i][j+1][nx][ny]=max(dp[i][j+1][nx][ny],dp[i][j][x][y]+(ny-nx+1));
                                ans=max(ans,dp[i][j+1][nx][ny]);
                            }
                        }
                    }
                }
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory 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 0 ms 448 KB ok
6 Correct 2 ms 3932 KB ok
7 Runtime error 5 ms 8028 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 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 2 ms 3928 KB ok
4 Correct 2 ms 3932 KB ok
5 Correct 2 ms 3932 KB ok
6 Correct 2 ms 3932 KB ok
7 Correct 2 ms 3932 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 344 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 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 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 3932 KB ok
6 Correct 2 ms 3932 KB ok
7 Correct 2 ms 3932 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 344 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 0 ms 348 KB ok
15 Correct 2 ms 3928 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 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 2 ms 3932 KB ok
23 Correct 2 ms 3932 KB ok
24 Correct 2 ms 3932 KB ok
25 Correct 2 ms 3932 KB ok
26 Correct 2 ms 3932 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 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 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 0 ms 348 KB ok
12 Correct 1 ms 344 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 0 ms 348 KB ok
17 Correct 2 ms 3928 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 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 2 ms 3932 KB ok
25 Correct 2 ms 3932 KB ok
26 Correct 2 ms 3932 KB ok
27 Correct 2 ms 3932 KB ok
28 Correct 2 ms 3932 KB ok
29 Correct 2 ms 3928 KB ok
30 Correct 3 ms 3932 KB ok
31 Correct 2 ms 3932 KB ok
32 Correct 2 ms 3932 KB ok
33 Correct 2 ms 3932 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 2 ms 3932 KB ok
37 Correct 3 ms 3932 KB ok
38 Correct 4 ms 4056 KB ok
39 Correct 3 ms 3932 KB ok
40 Correct 16 ms 3932 KB ok
41 Correct 10 ms 3928 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 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 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 0 ms 348 KB ok
12 Correct 1 ms 344 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 0 ms 348 KB ok
17 Correct 2 ms 3928 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 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 2 ms 3932 KB ok
25 Correct 2 ms 3932 KB ok
26 Correct 2 ms 3932 KB ok
27 Correct 2 ms 3932 KB ok
28 Correct 2 ms 3932 KB ok
29 Correct 2 ms 3928 KB ok
30 Correct 3 ms 3932 KB ok
31 Correct 2 ms 3932 KB ok
32 Correct 2 ms 3932 KB ok
33 Correct 2 ms 3932 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 2 ms 3932 KB ok
37 Correct 3 ms 3932 KB ok
38 Correct 4 ms 4056 KB ok
39 Correct 3 ms 3932 KB ok
40 Correct 16 ms 3932 KB ok
41 Correct 10 ms 3928 KB ok
42 Runtime error 19 ms 12528 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 2 ms 3928 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 0 ms 448 KB ok
7 Correct 2 ms 3932 KB ok
8 Runtime error 5 ms 8028 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -