oj.uz

Submission #1065101

# Submission time Handle Problem Language Result Execution time Memory
1065101 2024-08-18T22:41:47 Z vjudge1 Soccer Stadium (IOI23_soccer) C++17
49.5 / 100
 202 ms 47392 KB 
#include "bits/stdc++.h"
using namespace std;
int pref[2010][2010],dp[31][31][31][31];
inline int allempty(int col,int l,int r){
    return pref[col][r]==pref[col][l-1];
}
int ifall(int N){
    vector<pair<int,int>>rng(N);
    int oth,oth2=oth=N*N;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(allempty(i,j,j))
        rng[i-1].second=j,rng[i-1].first+=!rng[i-1].first*j;
    else oth--,oth2--;
    for(auto[i,j]:rng)
        oth-=j-i+1;
    if(oth) return 0;
    for(auto[i,j]:rng)
        for(auto[i2,j2]:rng)
            if(i&&i2&&i<i2&&j<j2)
                return 0;
    for(auto&[i,j]:rng)
        j-=i-1;
    int dec=0;
    for(int i=1;i<N;i++)
        if(rng[i].second<rng[i-1].second)
            dec=1;
        else if(dec&&rng[i].second>rng[i-1].second)
            return 0;
    return oth2;
}
int biggest_stadium(int N, vector<vector<int>> F) {
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
        pref[i+1][j+1] = F[i][j]+pref[i+1][j];
    if(N>30) return ifall(N);
    memset(dp,-2,sizeof dp);
    int ans=0;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++)
        for(int k=j;k<=N;k++) if(allempty(i,j,k))
                ans=max(ans,dp[i][i][j][k]=k-j+1);
    for(int sz=1;sz<N;sz++) {
        for(int c2=sz+1;c2<=N;c2++){
            int c1=c2-sz;
            for(int l1=1;l1<=N;l1++){
                for(int r1=l1;r1<=N;r1++){
                    if(!allempty(c1,l1,r1))goto h1;
                    for(int l2=l1;l2;l2--) for(int r2=r1;r2<=N;r2++)
                        dp[c1][c2][l1][r1]=max(dp[c1][c2][l1][r1],dp[c1+1][c2][l2][r2]);
                    h1:
                    if(!allempty(c2,l1,r1))goto h2;
                    for(int l2=l1;l2;l2--) for(int r2=r1;r2<=N;r2++)
                        dp[c1][c2][l1][r1]=max(dp[c1][c2][l1][r1],dp[c1][c2-1][l2][r2]);
                    h2:
                    ans=max(ans,dp[c1][c2][l1][r1]+=r1-l1+1);
                }
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok

Subtask #1
1.5 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB ok
2 Correct 2 ms 3932 KB ok
3 Correct 2 ms 3932 KB ok
4 Correct 1 ms 3932 KB ok
5 Correct 2 ms 3932 KB ok
6 Correct 1 ms 3932 KB ok
7 Partially correct 1 ms 856 KB partial
8 Partially correct 13 ms 5196 KB partial
9 Partially correct 202 ms 47392 KB partial

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB ok
2 Correct 2 ms 3932 KB ok
3 Correct 1 ms 3928 KB ok
4 Correct 2 ms 3932 KB ok
5 Correct 2 ms 3932 KB ok
6 Correct 1 ms 3928 KB ok
7 Correct 1 ms 3932 KB ok
8 Correct 1 ms 3932 KB ok
9 Correct 1 ms 3932 KB ok
10 Correct 2 ms 3932 KB ok
11 Correct 3 ms 3932 KB ok
12 Correct 2 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 2 ms 4184 KB ok
3 Correct 2 ms 3932 KB ok
4 Correct 1 ms 3928 KB ok
5 Correct 2 ms 3932 KB ok
6 Correct 2 ms 3932 KB ok
7 Correct 1 ms 3928 KB ok
8 Correct 1 ms 3932 KB ok
9 Correct 1 ms 3932 KB ok
10 Correct 1 ms 3932 KB ok
11 Correct 2 ms 3932 KB ok
12 Correct 3 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 2 ms 3932 KB ok
15 Correct 1 ms 3932 KB ok
16 Correct 2 ms 3928 KB ok
17 Correct 2 ms 3932 KB ok
18 Correct 1 ms 3932 KB ok
19 Correct 2 ms 3928 KB ok
20 Correct 2 ms 3932 KB ok
21 Correct 1 ms 3932 KB ok
22 Correct 2 ms 3928 KB ok
23 Correct 2 ms 3932 KB ok
24 Correct 1 ms 3932 KB ok
25 Correct 2 ms 3932 KB ok
26 Correct 1 ms 3932 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 2 ms 4184 KB ok
3 Correct 2 ms 3932 KB ok
4 Correct 2 ms 3932 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 1 ms 3928 KB ok
7 Correct 2 ms 3932 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 1 ms 3928 KB ok
10 Correct 1 ms 3932 KB ok
11 Correct 1 ms 3932 KB ok
12 Correct 1 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 3 ms 3932 KB ok
15 Correct 2 ms 3932 KB ok
16 Correct 2 ms 3932 KB ok
17 Correct 1 ms 3932 KB ok
18 Correct 2 ms 3928 KB ok
19 Correct 2 ms 3932 KB ok
20 Correct 1 ms 3932 KB ok
21 Correct 2 ms 3928 KB ok
22 Correct 2 ms 3932 KB ok
23 Correct 1 ms 3932 KB ok
24 Correct 2 ms 3928 KB ok
25 Correct 2 ms 3932 KB ok
26 Correct 1 ms 3932 KB ok
27 Correct 2 ms 3932 KB ok
28 Correct 1 ms 3932 KB ok
29 Correct 2 ms 3932 KB ok
30 Correct 19 ms 4188 KB ok
31 Correct 15 ms 4188 KB ok
32 Correct 7 ms 4180 KB ok
33 Correct 2 ms 4188 KB ok
34 Correct 4 ms 4188 KB ok
35 Correct 8 ms 4188 KB ok
36 Correct 4 ms 3932 KB ok
37 Correct 7 ms 4188 KB ok
38 Correct 6 ms 3932 KB ok
39 Correct 5 ms 4184 KB ok
40 Correct 17 ms 3932 KB ok
41 Correct 21 ms 3928 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 2 ms 4184 KB ok
3 Correct 2 ms 3932 KB ok
4 Correct 2 ms 3932 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 1 ms 3928 KB ok
7 Correct 2 ms 3932 KB ok
8 Correct 2 ms 3932 KB ok
9 Correct 1 ms 3928 KB ok
10 Correct 1 ms 3932 KB ok
11 Correct 1 ms 3932 KB ok
12 Correct 1 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 3 ms 3932 KB ok
15 Correct 2 ms 3932 KB ok
16 Correct 2 ms 3932 KB ok
17 Correct 1 ms 3932 KB ok
18 Correct 2 ms 3928 KB ok
19 Correct 2 ms 3932 KB ok
20 Correct 1 ms 3932 KB ok
21 Correct 2 ms 3928 KB ok
22 Correct 2 ms 3932 KB ok
23 Correct 1 ms 3932 KB ok
24 Correct 2 ms 3928 KB ok
25 Correct 2 ms 3932 KB ok
26 Correct 1 ms 3932 KB ok
27 Correct 2 ms 3932 KB ok
28 Correct 1 ms 3932 KB ok
29 Correct 2 ms 3932 KB ok
30 Correct 19 ms 4188 KB ok
31 Correct 15 ms 4188 KB ok
32 Correct 7 ms 4180 KB ok
33 Correct 2 ms 4188 KB ok
34 Correct 4 ms 4188 KB ok
35 Correct 8 ms 4188 KB ok
36 Correct 4 ms 3932 KB ok
37 Correct 7 ms 4188 KB ok
38 Correct 6 ms 3932 KB ok
39 Correct 5 ms 4184 KB ok
40 Correct 17 ms 3932 KB ok
41 Correct 21 ms 3928 KB ok
42 Partially correct 18 ms 5212 KB partial
43 Partially correct 15 ms 5212 KB partial
44 Partially correct 15 ms 5280 KB partial
45 Partially correct 13 ms 5280 KB partial
46 Partially correct 15 ms 5280 KB partial
47 Partially correct 15 ms 5212 KB partial
48 Incorrect 21 ms 5280 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 2 ms 4184 KB ok
3 Correct 2 ms 3932 KB ok
4 Correct 2 ms 3932 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 2 ms 3932 KB ok
7 Correct 1 ms 3932 KB ok
8 Partially correct 1 ms 856 KB partial
9 Partially correct 13 ms 5196 KB partial
10 Partially correct 202 ms 47392 KB partial
11 Correct 1 ms 3928 KB ok
12 Correct 2 ms 3932 KB ok
13 Correct 2 ms 3932 KB ok
14 Correct 1 ms 3928 KB ok
15 Correct 1 ms 3932 KB ok
16 Correct 1 ms 3932 KB ok
17 Correct 1 ms 3932 KB ok
18 Correct 2 ms 3932 KB ok
19 Correct 3 ms 3932 KB ok
20 Correct 2 ms 3932 KB ok
21 Correct 2 ms 3932 KB ok
22 Correct 1 ms 3932 KB ok
23 Correct 2 ms 3928 KB ok
24 Correct 2 ms 3932 KB ok
25 Correct 1 ms 3932 KB ok
26 Correct 2 ms 3928 KB ok
27 Correct 2 ms 3932 KB ok
28 Correct 1 ms 3932 KB ok
29 Correct 2 ms 3928 KB ok
30 Correct 2 ms 3932 KB ok
31 Correct 1 ms 3932 KB ok
32 Correct 2 ms 3932 KB ok
33 Correct 1 ms 3932 KB ok
34 Correct 2 ms 3932 KB ok
35 Correct 19 ms 4188 KB ok
36 Correct 15 ms 4188 KB ok
37 Correct 7 ms 4180 KB ok
38 Correct 2 ms 4188 KB ok
39 Correct 4 ms 4188 KB ok
40 Correct 8 ms 4188 KB ok
41 Correct 4 ms 3932 KB ok
42 Correct 7 ms 4188 KB ok
43 Correct 6 ms 3932 KB ok
44 Correct 5 ms 4184 KB ok
45 Correct 17 ms 3932 KB ok
46 Correct 21 ms 3928 KB ok
47 Partially correct 18 ms 5212 KB partial
48 Partially correct 15 ms 5212 KB partial
49 Partially correct 15 ms 5280 KB partial
50 Partially correct 13 ms 5280 KB partial
51 Partially correct 15 ms 5280 KB partial
52 Partially correct 15 ms 5212 KB partial
53 Incorrect 21 ms 5280 KB wrong
54 Halted 0 ms 0 KB -