oj.uz

Submission #1065091

# Submission time Handle Problem Language Result Execution time Memory
1065091 2024-08-18T22:32:43 Z vjudge1 Soccer Stadium (IOI23_soccer) C++17
48 / 100
 20 ms 4888 KB 
#include "bits/stdc++.h"
using namespace std;
int pref[31][31],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?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&&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=0;
        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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 1 ms 3932 KB ok
3 Correct 1 ms 3932 KB ok
4 Correct 1 ms 3932 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 1 ms 3932 KB ok
7 Partially correct 1 ms 456 KB partial
8 Runtime error 14 ms 4888 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 1 ms 3932 KB ok
3 Correct 1 ms 3928 KB ok
4 Correct 1 ms 3932 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 1 ms 3932 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 1 ms 3932 KB ok
11 Correct 1 ms 4024 KB ok
12 Correct 1 ms 3932 KB ok
13 Correct 1 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 1 ms 3932 KB ok
3 Correct 1 ms 3932 KB ok
4 Correct 1 ms 3928 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 1 ms 3932 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 1 ms 3932 KB ok
11 Correct 1 ms 3932 KB ok
12 Correct 1 ms 4024 KB ok
13 Correct 1 ms 3932 KB ok
14 Correct 1 ms 3932 KB ok
15 Correct 1 ms 3932 KB ok
16 Correct 1 ms 4060 KB ok
17 Correct 1 ms 3932 KB ok
18 Correct 1 ms 3932 KB ok
19 Correct 1 ms 3932 KB ok
20 Correct 1 ms 3928 KB ok
21 Correct 1 ms 3932 KB ok
22 Correct 1 ms 3932 KB ok
23 Correct 1 ms 3932 KB ok
24 Correct 1 ms 3932 KB ok
25 Correct 1 ms 3928 KB ok
26 Correct 2 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 1 ms 3932 KB ok
3 Correct 1 ms 3932 KB ok
4 Correct 1 ms 3932 KB ok
5 Correct 1 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 1 ms 3932 KB ok
11 Correct 1 ms 3932 KB ok
12 Correct 1 ms 3932 KB ok
13 Correct 1 ms 3932 KB ok
14 Correct 1 ms 4024 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 1 ms 4060 KB ok
19 Correct 1 ms 3932 KB ok
20 Correct 1 ms 3932 KB ok
21 Correct 1 ms 3932 KB ok
22 Correct 1 ms 3928 KB ok
23 Correct 1 ms 3932 KB ok
24 Correct 1 ms 3932 KB ok
25 Correct 1 ms 3932 KB ok
26 Correct 1 ms 3932 KB ok
27 Correct 1 ms 3928 KB ok
28 Correct 2 ms 3932 KB ok
29 Correct 1 ms 3932 KB ok
30 Correct 14 ms 4060 KB ok
31 Correct 10 ms 4020 KB ok
32 Correct 5 ms 3928 KB ok
33 Correct 2 ms 3932 KB ok
34 Correct 4 ms 3932 KB ok
35 Correct 8 ms 3932 KB ok
36 Correct 3 ms 3932 KB ok
37 Correct 4 ms 3932 KB ok
38 Correct 4 ms 4056 KB ok
39 Correct 5 ms 3932 KB ok
40 Correct 19 ms 4064 KB ok
41 Correct 20 ms 4064 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ok
2 Correct 1 ms 3932 KB ok
3 Correct 1 ms 3932 KB ok
4 Correct 1 ms 3932 KB ok
5 Correct 1 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 1 ms 3932 KB ok
11 Correct 1 ms 3932 KB ok
12 Correct 1 ms 3932 KB ok
13 Correct 1 ms 3932 KB ok
14 Correct 1 ms 4024 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 1 ms 4060 KB ok
19 Correct 1 ms 3932 KB ok
20 Correct 1 ms 3932 KB ok
21 Correct 1 ms 3932 KB ok
22 Correct 1 ms 3928 KB ok
23 Correct 1 ms 3932 KB ok
24 Correct 1 ms 3932 KB ok
25 Correct 1 ms 3932 KB ok
26 Correct 1 ms 3932 KB ok
27 Correct 1 ms 3928 KB ok
28 Correct 2 ms 3932 KB ok
29 Correct 1 ms 3932 KB ok
30 Correct 14 ms 4060 KB ok
31 Correct 10 ms 4020 KB ok
32 Correct 5 ms 3928 KB ok
33 Correct 2 ms 3932 KB ok
34 Correct 4 ms 3932 KB ok
35 Correct 8 ms 3932 KB ok
36 Correct 3 ms 3932 KB ok
37 Correct 4 ms 3932 KB ok
38 Correct 4 ms 4056 KB ok
39 Correct 5 ms 3932 KB ok
40 Correct 19 ms 4064 KB ok
41 Correct 20 ms 4064 KB ok
42 Runtime error 14 ms 4884 KB Execution killed with signal 11
43 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 1 ms 3932 KB ok
3 Correct 1 ms 3932 KB ok
4 Correct 1 ms 3932 KB ok
5 Correct 1 ms 3932 KB ok
6 Correct 1 ms 3932 KB ok
7 Correct 1 ms 3932 KB ok
8 Partially correct 1 ms 456 KB partial
9 Runtime error 14 ms 4888 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -