oj.uz

답안 #1079517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079517 2024-08-28T16:18:02 Z Huseyn123 축구 경기장 (IOI23_soccer) C++17
70 / 100
 663 ms 499072 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dp[501][501][501];
int r[501][501][501];
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int n=N;
    int cnt,x,y; 
    cnt=x=y=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(F[i][j]){
                x=i; 
                y=j; 
                cnt++; 
            }
        }
    }
    if(cnt==1){
        return N*N-min(x+1,N-x)*min(y+1,N-y);
    }
    int res=0; 
    for(int i=0;i<N;i++){
        int l=0; 
        for(int j=0;j<N;j++){
            if(F[i][j]){
                l=j+1;
            }
            else{
                r[i][i][l]=j;
                dp[i][i][l]=j-l+1;
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<N;j++){
            int z=j+i-1;
            if(j){
                for(int k=0;k<N;k++){
                    if(dp[j][z][k]){
                        int l=k;
                        for(int ind=k;ind<=r[j][z][k];ind++){
                            if(F[j-1][ind]){
                                l=ind+1;
                            }
                            else{
                                dp[j-1][z][l]=max(dp[j-1][z][l],ind-l+1+dp[j][z][k]);
                                r[j-1][z][l]=ind; 
                            }
                        }
                    }
                }
            }
            if(z+1<N){
                for(int k=0;k<N;k++){
                    if(dp[j][z][k]){
                        int l=k;
                        for(int ind=k;ind<=r[j][z][k];ind++){
                            if(F[z+1][ind]){
                                l=ind+1;
                            }
                            else{
                                dp[j][z+1][l]=max(dp[j][z+1][l],ind-l+1+dp[j][z][k]);
                                r[j][z+1][l]=ind; 
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++){
            for(int z=0;z<N;z++){
                res=max(res,dp[i][j][z]); 
            }
        }
    }
    return res; 
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:8:9: warning: unused variable 'n' [-Wunused-variable]
    8 |     int n=N;
      |         ^

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 14 ms 2908 KB ok
9 Correct 197 ms 39508 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 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.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 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 600 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 444 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 488 KB ok

Subtask #4
18.0 / 18.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 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 444 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 488 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 1 ms 2396 KB ok
31 Correct 2 ms 2140 KB ok
32 Correct 1 ms 1116 KB ok
33 Correct 1 ms 704 KB ok
34 Correct 1 ms 2140 KB ok
35 Correct 1 ms 1372 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 1116 KB ok
38 Correct 1 ms 1116 KB ok
39 Correct 1 ms 1372 KB ok
40 Correct 1 ms 1628 KB ok
41 Correct 2 ms 2392 KB ok

Subtask #5
16.0 / 16.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 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 444 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 488 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 1 ms 2396 KB ok
31 Correct 2 ms 2140 KB ok
32 Correct 1 ms 1116 KB ok
33 Correct 1 ms 704 KB ok
34 Correct 1 ms 2140 KB ok
35 Correct 1 ms 1372 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 1116 KB ok
38 Correct 1 ms 1116 KB ok
39 Correct 1 ms 1372 KB ok
40 Correct 1 ms 1628 KB ok
41 Correct 2 ms 2392 KB ok
42 Correct 321 ms 121028 KB ok
43 Correct 274 ms 65360 KB ok
44 Correct 644 ms 498764 KB ok
45 Correct 609 ms 499028 KB ok
46 Correct 392 ms 255316 KB ok
47 Correct 663 ms 498488 KB ok
48 Correct 492 ms 485716 KB ok
49 Correct 494 ms 447556 KB ok
50 Correct 528 ms 499072 KB ok
51 Correct 376 ms 252764 KB ok
52 Correct 275 ms 159560 KB ok
53 Correct 207 ms 44208 KB ok
54 Correct 358 ms 178772 KB ok
55 Correct 437 ms 403712 KB ok
56 Correct 271 ms 124500 KB ok
57 Correct 547 ms 498000 KB ok
58 Correct 543 ms 494676 KB ok
59 Correct 557 ms 477900 KB ok

Subtask #6
0.0 / 30.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 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 14 ms 2908 KB ok
10 Correct 197 ms 39508 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 600 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 444 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 488 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 2396 KB ok
36 Correct 2 ms 2140 KB ok
37 Correct 1 ms 1116 KB ok
38 Correct 1 ms 704 KB ok
39 Correct 1 ms 2140 KB ok
40 Correct 1 ms 1372 KB ok
41 Correct 1 ms 1116 KB ok
42 Correct 1 ms 1116 KB ok
43 Correct 1 ms 1116 KB ok
44 Correct 1 ms 1372 KB ok
45 Correct 1 ms 1628 KB ok
46 Correct 2 ms 2392 KB ok
47 Correct 321 ms 121028 KB ok
48 Correct 274 ms 65360 KB ok
49 Correct 644 ms 498764 KB ok
50 Correct 609 ms 499028 KB ok
51 Correct 392 ms 255316 KB ok
52 Correct 663 ms 498488 KB ok
53 Correct 492 ms 485716 KB ok
54 Correct 494 ms 447556 KB ok
55 Correct 528 ms 499072 KB ok
56 Correct 376 ms 252764 KB ok
57 Correct 275 ms 159560 KB ok
58 Correct 207 ms 44208 KB ok
59 Correct 358 ms 178772 KB ok
60 Correct 437 ms 403712 KB ok
61 Correct 271 ms 124500 KB ok
62 Correct 547 ms 498000 KB ok
63 Correct 543 ms 494676 KB ok
64 Correct 557 ms 477900 KB ok
65 Runtime error 261 ms 56176 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -