oj.uz

답안 #939396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939396 2024-03-06T10:21:50 Z Wansur 축구 경기장 (IOI23_soccer) C++17
49.5 / 100
 4500 ms 1028948 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[mx][mx];
int a[mx][mx];
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>> B) {
    n = N;
    if (n > 500) {
        return 0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=B[i][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;
            }
        }
    }

    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(ptr[i][l][r]==-1){
                    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 14684 KB ok

Subtask #1
1.5 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 2 ms 10588 KB ok
3 Correct 3 ms 22876 KB ok
4 Correct 4 ms 26972 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 45 ms 159828 KB ok
8 Correct 1711 ms 1028332 KB ok
9 Partially correct 223 ms 39572 KB partial

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 2 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 1 ms 10696 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 2 ms 10588 KB ok
14 Correct 2 ms 10588 KB ok
15 Correct 3 ms 18780 KB ok
16 Correct 3 ms 18780 KB ok
17 Correct 3 ms 19032 KB ok
18 Correct 3 ms 18884 KB ok
19 Correct 2 ms 18776 KB ok
20 Correct 2 ms 18776 KB ok
21 Correct 2 ms 18780 KB ok
22 Correct 3 ms 18776 KB ok
23 Correct 2 ms 18780 KB ok
24 Correct 3 ms 18776 KB ok
25 Correct 2 ms 18780 KB ok
26 Correct 2 ms 18780 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 4 ms 26972 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 2 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10696 KB ok
13 Correct 2 ms 10584 KB ok
14 Correct 2 ms 10588 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 2 ms 10588 KB ok
17 Correct 3 ms 18780 KB ok
18 Correct 3 ms 18780 KB ok
19 Correct 3 ms 19032 KB ok
20 Correct 3 ms 18884 KB ok
21 Correct 2 ms 18776 KB ok
22 Correct 2 ms 18776 KB ok
23 Correct 2 ms 18780 KB ok
24 Correct 3 ms 18776 KB ok
25 Correct 2 ms 18780 KB ok
26 Correct 3 ms 18776 KB ok
27 Correct 2 ms 18780 KB ok
28 Correct 2 ms 18780 KB ok
29 Correct 3 ms 18776 KB ok
30 Correct 8 ms 70232 KB ok
31 Correct 8 ms 70080 KB ok
32 Correct 9 ms 70236 KB ok
33 Correct 8 ms 70316 KB ok
34 Correct 8 ms 70236 KB ok
35 Correct 8 ms 70232 KB ok
36 Correct 8 ms 70236 KB ok
37 Correct 8 ms 70236 KB ok
38 Correct 8 ms 70236 KB ok
39 Correct 8 ms 70236 KB ok
40 Correct 8 ms 70084 KB ok
41 Correct 9 ms 70236 KB ok

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 4 ms 26972 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 2 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10696 KB ok
13 Correct 2 ms 10584 KB ok
14 Correct 2 ms 10588 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 2 ms 10588 KB ok
17 Correct 3 ms 18780 KB ok
18 Correct 3 ms 18780 KB ok
19 Correct 3 ms 19032 KB ok
20 Correct 3 ms 18884 KB ok
21 Correct 2 ms 18776 KB ok
22 Correct 2 ms 18776 KB ok
23 Correct 2 ms 18780 KB ok
24 Correct 3 ms 18776 KB ok
25 Correct 2 ms 18780 KB ok
26 Correct 3 ms 18776 KB ok
27 Correct 2 ms 18780 KB ok
28 Correct 2 ms 18780 KB ok
29 Correct 3 ms 18776 KB ok
30 Correct 8 ms 70232 KB ok
31 Correct 8 ms 70080 KB ok
32 Correct 9 ms 70236 KB ok
33 Correct 8 ms 70316 KB ok
34 Correct 8 ms 70236 KB ok
35 Correct 8 ms 70232 KB ok
36 Correct 8 ms 70236 KB ok
37 Correct 8 ms 70236 KB ok
38 Correct 8 ms 70236 KB ok
39 Correct 8 ms 70236 KB ok
40 Correct 8 ms 70084 KB ok
41 Correct 9 ms 70236 KB ok
42 Correct 1628 ms 1028944 KB ok
43 Correct 1520 ms 1028948 KB ok
44 Correct 2481 ms 1028824 KB ok
45 Correct 2896 ms 1028828 KB ok
46 Correct 1761 ms 1028824 KB ok
47 Correct 1659 ms 1028368 KB ok
48 Correct 1435 ms 1028436 KB ok
49 Correct 1530 ms 1028436 KB ok
50 Execution timed out 4591 ms 1028696 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 4 ms 26972 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 45 ms 159828 KB ok
9 Correct 1711 ms 1028332 KB ok
10 Partially correct 223 ms 39572 KB partial
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 1 ms 10696 KB ok
18 Correct 2 ms 10584 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 2 ms 10588 KB ok
22 Correct 3 ms 18780 KB ok
23 Correct 3 ms 18780 KB ok
24 Correct 3 ms 19032 KB ok
25 Correct 3 ms 18884 KB ok
26 Correct 2 ms 18776 KB ok
27 Correct 2 ms 18776 KB ok
28 Correct 2 ms 18780 KB ok
29 Correct 3 ms 18776 KB ok
30 Correct 2 ms 18780 KB ok
31 Correct 3 ms 18776 KB ok
32 Correct 2 ms 18780 KB ok
33 Correct 2 ms 18780 KB ok
34 Correct 3 ms 18776 KB ok
35 Correct 8 ms 70232 KB ok
36 Correct 8 ms 70080 KB ok
37 Correct 9 ms 70236 KB ok
38 Correct 8 ms 70316 KB ok
39 Correct 8 ms 70236 KB ok
40 Correct 8 ms 70232 KB ok
41 Correct 8 ms 70236 KB ok
42 Correct 8 ms 70236 KB ok
43 Correct 8 ms 70236 KB ok
44 Correct 8 ms 70236 KB ok
45 Correct 8 ms 70084 KB ok
46 Correct 9 ms 70236 KB ok
47 Correct 1628 ms 1028944 KB ok
48 Correct 1520 ms 1028948 KB ok
49 Correct 2481 ms 1028824 KB ok
50 Correct 2896 ms 1028828 KB ok
51 Correct 1761 ms 1028824 KB ok
52 Correct 1659 ms 1028368 KB ok
53 Correct 1435 ms 1028436 KB ok
54 Correct 1530 ms 1028436 KB ok
55 Execution timed out 4591 ms 1028696 KB Time limit exceeded
56 Halted 0 ms 0 KB -