oj.uz

답안 #1018106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018106 2024-07-09T14:27:22 Z kym 축구 경기장 (IOI23_soccer) C++17
48 / 100
 23 ms 12024 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)
{
    if(n==1){
        if(F[0][0] == 0)return 1;
        else return 0;
    }
    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

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

Subtask #1
0.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 1 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 2 ms 3832 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

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 348 KB ok
6 Correct 1 ms 3932 KB ok
7 Correct 1 ms 3932 KB ok
8 Correct 1 ms 3932 KB ok
9 Correct 1 ms 3932 KB ok
10 Correct 1 ms 3932 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 3932 KB ok
14 Correct 1 ms 3932 KB ok
15 Correct 1 ms 3988 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 3932 KB ok
18 Correct 1 ms 3932 KB ok
19 Correct 1 ms 3928 KB ok
20 Correct 1 ms 3804 KB ok
21 Correct 1 ms 3932 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 3932 KB ok
25 Correct 2 ms 3928 KB ok
26 Correct 1 ms 3928 KB ok
27 Correct 1 ms 3932 KB ok
28 Correct 1 ms 3928 KB ok
29 Correct 1 ms 3932 KB ok
30 Correct 2 ms 3932 KB ok
31 Correct 2 ms 3932 KB ok
32 Correct 2 ms 3928 KB ok
33 Correct 1 ms 3932 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 2 ms 3932 KB ok
37 Correct 2 ms 3932 KB ok
38 Correct 2 ms 3932 KB ok
39 Correct 2 ms 3932 KB ok
40 Correct 23 ms 3932 KB ok
41 Correct 9 ms 3932 KB ok

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 348 KB ok
6 Correct 1 ms 3932 KB ok
7 Correct 1 ms 3932 KB ok
8 Correct 1 ms 3932 KB ok
9 Correct 1 ms 3932 KB ok
10 Correct 1 ms 3932 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 3932 KB ok
14 Correct 1 ms 3932 KB ok
15 Correct 1 ms 3988 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 3932 KB ok
18 Correct 1 ms 3932 KB ok
19 Correct 1 ms 3928 KB ok
20 Correct 1 ms 3804 KB ok
21 Correct 1 ms 3932 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 3932 KB ok
25 Correct 2 ms 3928 KB ok
26 Correct 1 ms 3928 KB ok
27 Correct 1 ms 3932 KB ok
28 Correct 1 ms 3928 KB ok
29 Correct 1 ms 3932 KB ok
30 Correct 2 ms 3932 KB ok
31 Correct 2 ms 3932 KB ok
32 Correct 2 ms 3928 KB ok
33 Correct 1 ms 3932 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 2 ms 3932 KB ok
37 Correct 2 ms 3932 KB ok
38 Correct 2 ms 3932 KB ok
39 Correct 2 ms 3932 KB ok
40 Correct 23 ms 3932 KB ok
41 Correct 9 ms 3932 KB ok
42 Runtime error 17 ms 12024 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 2 ms 3832 KB ok
8 Runtime error 5 ms 8028 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -