oj.uz

Submission #916616

# Submission time Handle Problem Language Result Execution time Memory
916616 2024-01-26T07:19:08 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 883792 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=32,inf=1e9;
int n,res;
unordered_map <int, int> dp[2][mxn][mxn][mxn][mxn];
vector <vector <int>> s;
int sum(int i, int l, int r){
    return s[i][r]-s[i][l-1];
}
int f(int b, int i, int j, int l, int r, int u, int v){
    if (i<0||j>n+1||l>r||u>v||!((l>=u&&r<=v)||(l<=u&&r>=v)))
        return -inf;
    if (dp[b][l][r][u][v].count(i*(n+2)+j))
        return dp[b][l][r][u][v][i*(n+2)+j];
    int res=0;
    if (!b)
        res=f(1,i,j,l,r,u,v);
    int x=(r-l+1>v-u+1?i:j);
    if (b)
        x=i^j^x;
    if (x==i){
        res=max(res,max(f(b,i,j,l+1,r,u,v),f(b,i,j,l,r-1,u,v)));
        if (!sum(i,l,r))
            res=max(res,f(b,i-1,j,l,r,u,v)+r-l+1);
    }
    else{
        res=max(res,max(f(b,i,j,l,r,u+1,v),f(b,i,j,l,r,u,v-1)));
        if (!sum(j,u,v))
            res=max(res,f(b,i,j+1,l,r,u,v)+v-u+1);
    }
    return dp[b][l][r][u][v][i*(n+2)+j]=res;
}
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    s.resize(N+2);
    for (int i=0;i<N+2;i++){
        s[i].assign(N+2,0);
        if (i&&i<N+1)
            for (int j=1;j<=N;j++)
                s[i][j]=s[i][j-1]+F[i-1][j-1];
    }
    for (int i=1;i<=N;i++){
        int cur=-1;
        for (int j=0;j<N;j++){
            if (F[i-1][j])
                cur=j;
            res=max(res,j-cur);
        }
        if (i<N)
            res=max(res,f(0,i,i+1,1,N,1,N));
    }
    return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115284 KB ok
2 Correct 38 ms 115292 KB ok
3 Correct 45 ms 117504 KB ok
4 Correct 54 ms 119636 KB ok
5 Correct 39 ms 115288 KB ok
6 Correct 37 ms 115120 KB ok
7 Runtime error 137 ms 234108 KB Execution killed with signal 8
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115284 KB ok
2 Correct 38 ms 115292 KB ok
3 Correct 36 ms 115288 KB ok
4 Correct 37 ms 115164 KB ok
5 Correct 37 ms 115292 KB ok
6 Correct 37 ms 115200 KB ok
7 Correct 37 ms 115200 KB ok
8 Correct 42 ms 115128 KB ok
9 Correct 39 ms 115292 KB ok
10 Correct 37 ms 115144 KB ok
11 Correct 36 ms 115292 KB ok
12 Correct 38 ms 115340 KB ok
13 Correct 37 ms 115292 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115280 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 38 ms 115292 KB ok
4 Correct 36 ms 115288 KB ok
5 Correct 37 ms 115164 KB ok
6 Correct 37 ms 115292 KB ok
7 Correct 37 ms 115200 KB ok
8 Correct 37 ms 115200 KB ok
9 Correct 42 ms 115128 KB ok
10 Correct 39 ms 115292 KB ok
11 Correct 37 ms 115144 KB ok
12 Correct 36 ms 115292 KB ok
13 Correct 38 ms 115340 KB ok
14 Correct 37 ms 115292 KB ok
15 Correct 38 ms 115920 KB ok
16 Correct 39 ms 115636 KB ok
17 Correct 39 ms 115540 KB ok
18 Correct 37 ms 115292 KB ok
19 Correct 38 ms 115480 KB ok
20 Correct 39 ms 115284 KB ok
21 Correct 41 ms 115536 KB ok
22 Correct 38 ms 115292 KB ok
23 Correct 38 ms 115280 KB ok
24 Correct 38 ms 115288 KB ok
25 Correct 39 ms 115464 KB ok
26 Correct 38 ms 115596 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115280 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 38 ms 115292 KB ok
4 Correct 45 ms 117504 KB ok
5 Correct 54 ms 119636 KB ok
6 Correct 36 ms 115288 KB ok
7 Correct 37 ms 115164 KB ok
8 Correct 37 ms 115292 KB ok
9 Correct 37 ms 115200 KB ok
10 Correct 37 ms 115200 KB ok
11 Correct 42 ms 115128 KB ok
12 Correct 39 ms 115292 KB ok
13 Correct 37 ms 115144 KB ok
14 Correct 36 ms 115292 KB ok
15 Correct 38 ms 115340 KB ok
16 Correct 37 ms 115292 KB ok
17 Correct 38 ms 115920 KB ok
18 Correct 39 ms 115636 KB ok
19 Correct 39 ms 115540 KB ok
20 Correct 37 ms 115292 KB ok
21 Correct 38 ms 115480 KB ok
22 Correct 39 ms 115284 KB ok
23 Correct 41 ms 115536 KB ok
24 Correct 38 ms 115292 KB ok
25 Correct 38 ms 115280 KB ok
26 Correct 38 ms 115288 KB ok
27 Correct 39 ms 115464 KB ok
28 Correct 38 ms 115596 KB ok
29 Correct 38 ms 115792 KB ok
30 Correct 2216 ms 376880 KB ok
31 Correct 1969 ms 303272 KB ok
32 Correct 1379 ms 232196 KB ok
33 Correct 1035 ms 215888 KB ok
34 Correct 1372 ms 270700 KB ok
35 Correct 2267 ms 382120 KB ok
36 Correct 1105 ms 239144 KB ok
37 Correct 1577 ms 280036 KB ok
38 Correct 1560 ms 266104 KB ok
39 Correct 1743 ms 317076 KB ok
40 Execution timed out 4571 ms 883792 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115280 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 38 ms 115292 KB ok
4 Correct 45 ms 117504 KB ok
5 Correct 54 ms 119636 KB ok
6 Correct 36 ms 115288 KB ok
7 Correct 37 ms 115164 KB ok
8 Correct 37 ms 115292 KB ok
9 Correct 37 ms 115200 KB ok
10 Correct 37 ms 115200 KB ok
11 Correct 42 ms 115128 KB ok
12 Correct 39 ms 115292 KB ok
13 Correct 37 ms 115144 KB ok
14 Correct 36 ms 115292 KB ok
15 Correct 38 ms 115340 KB ok
16 Correct 37 ms 115292 KB ok
17 Correct 38 ms 115920 KB ok
18 Correct 39 ms 115636 KB ok
19 Correct 39 ms 115540 KB ok
20 Correct 37 ms 115292 KB ok
21 Correct 38 ms 115480 KB ok
22 Correct 39 ms 115284 KB ok
23 Correct 41 ms 115536 KB ok
24 Correct 38 ms 115292 KB ok
25 Correct 38 ms 115280 KB ok
26 Correct 38 ms 115288 KB ok
27 Correct 39 ms 115464 KB ok
28 Correct 38 ms 115596 KB ok
29 Correct 38 ms 115792 KB ok
30 Correct 2216 ms 376880 KB ok
31 Correct 1969 ms 303272 KB ok
32 Correct 1379 ms 232196 KB ok
33 Correct 1035 ms 215888 KB ok
34 Correct 1372 ms 270700 KB ok
35 Correct 2267 ms 382120 KB ok
36 Correct 1105 ms 239144 KB ok
37 Correct 1577 ms 280036 KB ok
38 Correct 1560 ms 266104 KB ok
39 Correct 1743 ms 317076 KB ok
40 Execution timed out 4571 ms 883792 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115280 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 38 ms 115292 KB ok
4 Correct 45 ms 117504 KB ok
5 Correct 54 ms 119636 KB ok
6 Correct 39 ms 115288 KB ok
7 Correct 37 ms 115120 KB ok
8 Runtime error 137 ms 234108 KB Execution killed with signal 8
9 Halted 0 ms 0 KB -