oj.uz

답안 #939379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939379 2024-03-06T10:09:37 Z Wansur 축구 경기장 (IOI23_soccer) C++17
49.5 / 100
 644 ms 1014612 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

typedef long long ll;
using namespace std;
struct seg{
    int m1,m2,sum,cnt;
};

const string out[2]={"NO\n","YES\n"};

const ll dx[]={0,1,0,-1,-1,1,1,-1};
const ll dy[]={1,0,-1,0,-1,1,-1,1};
const int mod=998244353;
const int md=1e9+7;
const int mx=2e3+12;
const bool T=0;

int ptr[512][512][512];
int dp[512][512][512];
int pref[512][512];
int n;

int get(int i,int l,int r){
    if(!l)return pref[i][r];
    return pref[i][r]-pref[i][l-1];
}

int biggest_stadium(int N, vector<vector<int>> a) {
    n = N;
    if (n > 500) {
        return 0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            pref[i][j]=a[i][j];
            if(j) pref[i][j]+=pref[i][j-1];
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                ptr[i][j][k]=-1;
                dp[i][j][k]=-1e9;
            }
        }
    }
    int ans=0;

    for(int l=0;l<n;l++){
        for(int r=l;r<n;r++){
            for(int i=0;i<n;i++){
                if(get(i,l,r)){
                    continue;
                }
                int j=i;
                while(j<n-1 && !get(j+1,l,r)){
                    j++;
                }
                ptr[i][l][r]=j;
                i=j;
            }
        }
    }
    if(n>30)return 0;

    for(int len=n;len>=1;len--){
        for(int l=0;l+len-1<n;l++){
            int r=l+len-1;
            for(int i=0;i<n;i++){
                if(get(i,l,r)>0){
                    continue;
                }
                int j=ptr[i][l][r];
                dp[i][l][r]=(j-i+1)*(r-l+1);
                for(int s=i;s<=j;s++) {
                    if(l>0 && ptr[s][l-1][r]!=-1){
                        int t=ptr[s][l-1][r];
                        dp[i][l][r]=max(dp[i][l][r], dp[s][l-1][r] + ((j-i+1) - (t-s+1)) * (r-l+1));
                    }
                    if(r<n-1 && ptr[s][l][r+1]!=-1){
                        int t=ptr[s][l][r+1];
                        dp[i][l][r]=max(dp[i][l][r], dp[s][l][r+1] + ((j-i+1) - (t-s+1)) * (r-l+1));
                    }
                }
                ans=max(ans,dp[i][l][r]);
                i=j;
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
1.5 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 2 ms 8540 KB ok
3 Correct 4 ms 20828 KB ok
4 Correct 5 ms 24924 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 8540 KB ok
7 Partially correct 30 ms 97872 KB partial
8 Partially correct 644 ms 1013840 KB partial
9 Partially correct 244 ms 35744 KB partial

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 2 ms 8540 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 2 ms 8536 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8636 KB ok
13 Correct 1 ms 8644 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 2 ms 8540 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 2 ms 8536 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8636 KB ok
14 Correct 1 ms 8644 KB ok
15 Correct 2 ms 16732 KB ok
16 Correct 2 ms 16732 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 2 ms 16728 KB ok
19 Correct 2 ms 16728 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 3 ms 16732 KB ok
25 Correct 3 ms 16732 KB ok
26 Correct 2 ms 16732 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 2 ms 8540 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 5 ms 24924 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 2 ms 8536 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8636 KB ok
16 Correct 1 ms 8644 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 2 ms 16732 KB ok
20 Correct 2 ms 16728 KB ok
21 Correct 2 ms 16728 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 16732 KB ok
25 Correct 2 ms 16732 KB ok
26 Correct 3 ms 16732 KB ok
27 Correct 3 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 2 ms 16984 KB ok
30 Correct 7 ms 66140 KB ok
31 Correct 7 ms 66136 KB ok
32 Correct 7 ms 66140 KB ok
33 Correct 7 ms 66140 KB ok
34 Correct 7 ms 66140 KB ok
35 Correct 7 ms 66140 KB ok
36 Correct 7 ms 66140 KB ok
37 Correct 7 ms 66140 KB ok
38 Correct 7 ms 66140 KB ok
39 Correct 7 ms 66140 KB ok
40 Correct 7 ms 66140 KB ok
41 Correct 7 ms 66140 KB ok

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 2 ms 8540 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 5 ms 24924 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 2 ms 8536 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8636 KB ok
16 Correct 1 ms 8644 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 2 ms 16732 KB ok
20 Correct 2 ms 16728 KB ok
21 Correct 2 ms 16728 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 16732 KB ok
25 Correct 2 ms 16732 KB ok
26 Correct 3 ms 16732 KB ok
27 Correct 3 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 2 ms 16984 KB ok
30 Correct 7 ms 66140 KB ok
31 Correct 7 ms 66136 KB ok
32 Correct 7 ms 66140 KB ok
33 Correct 7 ms 66140 KB ok
34 Correct 7 ms 66140 KB ok
35 Correct 7 ms 66140 KB ok
36 Correct 7 ms 66140 KB ok
37 Correct 7 ms 66140 KB ok
38 Correct 7 ms 66140 KB ok
39 Correct 7 ms 66140 KB ok
40 Correct 7 ms 66140 KB ok
41 Correct 7 ms 66140 KB ok
42 Partially correct 528 ms 1014100 KB partial
43 Partially correct 516 ms 1014496 KB partial
44 Partially correct 593 ms 1014036 KB partial
45 Partially correct 598 ms 1014096 KB partial
46 Partially correct 554 ms 1014148 KB partial
47 Partially correct 517 ms 1014612 KB partial
48 Incorrect 601 ms 1014100 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 2 ms 8540 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 5 ms 24924 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 8540 KB ok
8 Partially correct 30 ms 97872 KB partial
9 Partially correct 644 ms 1013840 KB partial
10 Partially correct 244 ms 35744 KB partial
11 Correct 1 ms 8536 KB ok
12 Correct 2 ms 8536 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8636 KB ok
21 Correct 1 ms 8644 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 16732 KB ok
25 Correct 2 ms 16728 KB ok
26 Correct 2 ms 16728 KB ok
27 Correct 2 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 2 ms 16732 KB ok
30 Correct 2 ms 16732 KB ok
31 Correct 3 ms 16732 KB ok
32 Correct 3 ms 16732 KB ok
33 Correct 2 ms 16732 KB ok
34 Correct 2 ms 16984 KB ok
35 Correct 7 ms 66140 KB ok
36 Correct 7 ms 66136 KB ok
37 Correct 7 ms 66140 KB ok
38 Correct 7 ms 66140 KB ok
39 Correct 7 ms 66140 KB ok
40 Correct 7 ms 66140 KB ok
41 Correct 7 ms 66140 KB ok
42 Correct 7 ms 66140 KB ok
43 Correct 7 ms 66140 KB ok
44 Correct 7 ms 66140 KB ok
45 Correct 7 ms 66140 KB ok
46 Correct 7 ms 66140 KB ok
47 Partially correct 528 ms 1014100 KB partial
48 Partially correct 516 ms 1014496 KB partial
49 Partially correct 593 ms 1014036 KB partial
50 Partially correct 598 ms 1014096 KB partial
51 Partially correct 554 ms 1014148 KB partial
52 Partially correct 517 ms 1014612 KB partial
53 Incorrect 601 ms 1014100 KB wrong
54 Halted 0 ms 0 KB -