oj.uz

답안 #939367

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

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

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[61][61];
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;
            }
        }
    }

    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 14680 KB ok

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10688 KB ok
2 Correct 2 ms 10588 KB ok
3 Correct 3 ms 22876 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 1 ms 6588 KB ok
6 Correct 1 ms 10688 KB ok
7 Execution timed out 4596 ms 71764 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10688 KB ok
2 Correct 2 ms 10588 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 2 ms 10584 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 2 ms 10708 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 10684 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10688 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 3 ms 22876 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 2 ms 10584 KB ok
8 Correct 2 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 2 ms 10708 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 2 ms 10588 KB ok
14 Correct 1 ms 10684 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 3 ms 18780 KB ok
18 Correct 2 ms 18780 KB ok
19 Correct 2 ms 18780 KB ok
20 Correct 3 ms 19036 KB ok
21 Correct 2 ms 18780 KB ok
22 Correct 2 ms 18780 KB ok
23 Correct 2 ms 18780 KB ok
24 Correct 3 ms 18780 KB ok
25 Correct 3 ms 18776 KB ok
26 Correct 3 ms 18780 KB ok
27 Correct 3 ms 18780 KB ok
28 Correct 2 ms 18780 KB ok
29 Correct 2 ms 18776 KB ok
30 Correct 6 ms 44892 KB ok
31 Correct 5 ms 42844 KB ok
32 Correct 6 ms 44888 KB ok
33 Correct 6 ms 42840 KB ok
34 Correct 5 ms 44892 KB ok
35 Correct 6 ms 41052 KB ok
36 Correct 5 ms 41052 KB ok
37 Correct 5 ms 39004 KB ok
38 Correct 5 ms 41052 KB ok
39 Correct 5 ms 41048 KB ok
40 Correct 5 ms 39000 KB ok
41 Correct 5 ms 39000 KB ok

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10688 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 3 ms 22876 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 2 ms 10584 KB ok
8 Correct 2 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 2 ms 10708 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 2 ms 10588 KB ok
14 Correct 1 ms 10684 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 3 ms 18780 KB ok
18 Correct 2 ms 18780 KB ok
19 Correct 2 ms 18780 KB ok
20 Correct 3 ms 19036 KB ok
21 Correct 2 ms 18780 KB ok
22 Correct 2 ms 18780 KB ok
23 Correct 2 ms 18780 KB ok
24 Correct 3 ms 18780 KB ok
25 Correct 3 ms 18776 KB ok
26 Correct 3 ms 18780 KB ok
27 Correct 3 ms 18780 KB ok
28 Correct 2 ms 18780 KB ok
29 Correct 2 ms 18776 KB ok
30 Correct 6 ms 44892 KB ok
31 Correct 5 ms 42844 KB ok
32 Correct 6 ms 44888 KB ok
33 Correct 6 ms 42840 KB ok
34 Correct 5 ms 44892 KB ok
35 Correct 6 ms 41052 KB ok
36 Correct 5 ms 41052 KB ok
37 Correct 5 ms 39004 KB ok
38 Correct 5 ms 41052 KB ok
39 Correct 5 ms 41048 KB ok
40 Correct 5 ms 39000 KB ok
41 Correct 5 ms 39000 KB ok
42 Execution timed out 4596 ms 1013508 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10688 KB ok
3 Correct 2 ms 10588 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 3 ms 22876 KB ok
6 Correct 1 ms 6588 KB ok
7 Correct 1 ms 10688 KB ok
8 Execution timed out 4596 ms 71764 KB Time limit exceeded
9 Halted 0 ms 0 KB -