oj.uz

답안 #939369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939369 2024-03-06T10:05:18 Z Wansur 축구 경기장 (IOI23_soccer) C++17
49.5 / 100
 4500 ms 1013856 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[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;
            }
        }
    }

    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 1 ms 8540 KB ok
3 Correct 4 ms 20828 KB ok
4 Correct 4 ms 24924 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 28 ms 76636 KB ok
8 Correct 1727 ms 1013836 KB ok
9 Partially correct 253 ms 39508 KB partial

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8648 KB ok
6 Correct 2 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 2 ms 8792 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 2 ms 8540 KB ok
13 Correct 1 ms 8540 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 1 ms 8540 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8536 KB ok
6 Correct 1 ms 8648 KB ok
7 Correct 2 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 2 ms 8792 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8536 KB ok
13 Correct 2 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 2 ms 16732 KB ok
16 Correct 3 ms 16732 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 3 ms 16728 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 3 ms 16732 KB ok
23 Correct 2 ms 16984 KB ok
24 Correct 2 ms 16884 KB ok
25 Correct 2 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 1 ms 8540 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 4 ms 24924 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8536 KB ok
8 Correct 1 ms 8648 KB ok
9 Correct 2 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 2 ms 8792 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 2 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 3 ms 16732 KB ok
19 Correct 2 ms 16732 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 3 ms 16728 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 2 ms 16984 KB ok
26 Correct 2 ms 16884 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 8 ms 50524 KB ok
31 Correct 6 ms 50520 KB ok
32 Correct 7 ms 52568 KB ok
33 Correct 6 ms 52572 KB ok
34 Correct 7 ms 50524 KB ok
35 Correct 6 ms 50524 KB ok
36 Correct 6 ms 50524 KB ok
37 Correct 6 ms 50524 KB ok
38 Correct 6 ms 52572 KB ok
39 Correct 6 ms 50524 KB ok
40 Correct 6 ms 50524 KB ok
41 Correct 6 ms 50688 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 1 ms 8540 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 4 ms 24924 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8536 KB ok
8 Correct 1 ms 8648 KB ok
9 Correct 2 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 2 ms 8792 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 2 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 3 ms 16732 KB ok
19 Correct 2 ms 16732 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 3 ms 16728 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 2 ms 16984 KB ok
26 Correct 2 ms 16884 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 8 ms 50524 KB ok
31 Correct 6 ms 50520 KB ok
32 Correct 7 ms 52568 KB ok
33 Correct 6 ms 52572 KB ok
34 Correct 7 ms 50524 KB ok
35 Correct 6 ms 50524 KB ok
36 Correct 6 ms 50524 KB ok
37 Correct 6 ms 50524 KB ok
38 Correct 6 ms 52572 KB ok
39 Correct 6 ms 50524 KB ok
40 Correct 6 ms 50524 KB ok
41 Correct 6 ms 50688 KB ok
42 Correct 894 ms 1013256 KB ok
43 Correct 780 ms 1013844 KB ok
44 Correct 2220 ms 1013828 KB ok
45 Correct 2788 ms 1013600 KB ok
46 Correct 1167 ms 1013788 KB ok
47 Correct 1636 ms 1013856 KB ok
48 Correct 950 ms 1013792 KB ok
49 Correct 1002 ms 1013788 KB ok
50 Execution timed out 4631 ms 1013724 KB Time limit exceeded
51 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 1 ms 8540 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 4 ms 24924 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 28 ms 76636 KB ok
9 Correct 1727 ms 1013836 KB ok
10 Partially correct 253 ms 39508 KB partial
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8536 KB ok
13 Correct 1 ms 8648 KB ok
14 Correct 2 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 2 ms 8792 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 2 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 3 ms 16732 KB ok
24 Correct 2 ms 16732 KB ok
25 Correct 2 ms 16732 KB ok
26 Correct 3 ms 16728 KB ok
27 Correct 2 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 3 ms 16732 KB ok
30 Correct 2 ms 16984 KB ok
31 Correct 2 ms 16884 KB ok
32 Correct 2 ms 16732 KB ok
33 Correct 2 ms 16732 KB ok
34 Correct 2 ms 16732 KB ok
35 Correct 8 ms 50524 KB ok
36 Correct 6 ms 50520 KB ok
37 Correct 7 ms 52568 KB ok
38 Correct 6 ms 52572 KB ok
39 Correct 7 ms 50524 KB ok
40 Correct 6 ms 50524 KB ok
41 Correct 6 ms 50524 KB ok
42 Correct 6 ms 50524 KB ok
43 Correct 6 ms 52572 KB ok
44 Correct 6 ms 50524 KB ok
45 Correct 6 ms 50524 KB ok
46 Correct 6 ms 50688 KB ok
47 Correct 894 ms 1013256 KB ok
48 Correct 780 ms 1013844 KB ok
49 Correct 2220 ms 1013828 KB ok
50 Correct 2788 ms 1013600 KB ok
51 Correct 1167 ms 1013788 KB ok
52 Correct 1636 ms 1013856 KB ok
53 Correct 950 ms 1013792 KB ok
54 Correct 1002 ms 1013788 KB ok
55 Execution timed out 4631 ms 1013724 KB Time limit exceeded
56 Halted 0 ms 0 KB -