oj.uz

Submission #916617

# Submission time Handle Problem Language Result Execution time Memory
916617 2024-01-26T07:22:23 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 883408 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){
        if (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 if (j<=n){
        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);
    }
    //cout << b << ' ' << i << ' ' << j << ' ' << l << ' ' << r << ' ' << u << ' ' << v << ' ' << res << '\n';
    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 39 ms 115292 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115284 KB ok
2 Correct 37 ms 115292 KB ok
3 Correct 49 ms 117332 KB ok
4 Correct 52 ms 119384 KB ok
5 Correct 39 ms 115292 KB ok
6 Correct 38 ms 115320 KB ok
7 Runtime error 126 ms 233880 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 37 ms 115292 KB ok
3 Correct 38 ms 115284 KB ok
4 Correct 38 ms 115188 KB ok
5 Correct 39 ms 115412 KB ok
6 Correct 39 ms 115320 KB ok
7 Correct 38 ms 115280 KB ok
8 Correct 38 ms 115292 KB ok
9 Correct 39 ms 115088 KB ok
10 Correct 41 ms 115288 KB ok
11 Correct 38 ms 115232 KB ok
12 Correct 38 ms 115292 KB ok
13 Correct 38 ms 115284 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 115292 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 37 ms 115292 KB ok
4 Correct 38 ms 115284 KB ok
5 Correct 38 ms 115188 KB ok
6 Correct 39 ms 115412 KB ok
7 Correct 39 ms 115320 KB ok
8 Correct 38 ms 115280 KB ok
9 Correct 38 ms 115292 KB ok
10 Correct 39 ms 115088 KB ok
11 Correct 41 ms 115288 KB ok
12 Correct 38 ms 115232 KB ok
13 Correct 38 ms 115292 KB ok
14 Correct 38 ms 115284 KB ok
15 Correct 39 ms 115804 KB ok
16 Correct 39 ms 115548 KB ok
17 Correct 39 ms 115548 KB ok
18 Correct 38 ms 115288 KB ok
19 Correct 37 ms 115292 KB ok
20 Correct 38 ms 115428 KB ok
21 Correct 38 ms 115292 KB ok
22 Correct 42 ms 115288 KB ok
23 Correct 38 ms 115388 KB ok
24 Correct 38 ms 115288 KB ok
25 Correct 40 ms 115548 KB ok
26 Correct 39 ms 115540 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 115292 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 37 ms 115292 KB ok
4 Correct 49 ms 117332 KB ok
5 Correct 52 ms 119384 KB ok
6 Correct 38 ms 115284 KB ok
7 Correct 38 ms 115188 KB ok
8 Correct 39 ms 115412 KB ok
9 Correct 39 ms 115320 KB ok
10 Correct 38 ms 115280 KB ok
11 Correct 38 ms 115292 KB ok
12 Correct 39 ms 115088 KB ok
13 Correct 41 ms 115288 KB ok
14 Correct 38 ms 115232 KB ok
15 Correct 38 ms 115292 KB ok
16 Correct 38 ms 115284 KB ok
17 Correct 39 ms 115804 KB ok
18 Correct 39 ms 115548 KB ok
19 Correct 39 ms 115548 KB ok
20 Correct 38 ms 115288 KB ok
21 Correct 37 ms 115292 KB ok
22 Correct 38 ms 115428 KB ok
23 Correct 38 ms 115292 KB ok
24 Correct 42 ms 115288 KB ok
25 Correct 38 ms 115388 KB ok
26 Correct 38 ms 115288 KB ok
27 Correct 40 ms 115548 KB ok
28 Correct 39 ms 115540 KB ok
29 Correct 39 ms 115544 KB ok
30 Correct 2158 ms 376852 KB ok
31 Correct 1905 ms 303488 KB ok
32 Correct 1262 ms 232388 KB ok
33 Correct 982 ms 216132 KB ok
34 Correct 1290 ms 270752 KB ok
35 Correct 2197 ms 382292 KB ok
36 Correct 1050 ms 239092 KB ok
37 Correct 1510 ms 279420 KB ok
38 Correct 1453 ms 266096 KB ok
39 Correct 1603 ms 316888 KB ok
40 Execution timed out 4610 ms 883408 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 115292 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 37 ms 115292 KB ok
4 Correct 49 ms 117332 KB ok
5 Correct 52 ms 119384 KB ok
6 Correct 38 ms 115284 KB ok
7 Correct 38 ms 115188 KB ok
8 Correct 39 ms 115412 KB ok
9 Correct 39 ms 115320 KB ok
10 Correct 38 ms 115280 KB ok
11 Correct 38 ms 115292 KB ok
12 Correct 39 ms 115088 KB ok
13 Correct 41 ms 115288 KB ok
14 Correct 38 ms 115232 KB ok
15 Correct 38 ms 115292 KB ok
16 Correct 38 ms 115284 KB ok
17 Correct 39 ms 115804 KB ok
18 Correct 39 ms 115548 KB ok
19 Correct 39 ms 115548 KB ok
20 Correct 38 ms 115288 KB ok
21 Correct 37 ms 115292 KB ok
22 Correct 38 ms 115428 KB ok
23 Correct 38 ms 115292 KB ok
24 Correct 42 ms 115288 KB ok
25 Correct 38 ms 115388 KB ok
26 Correct 38 ms 115288 KB ok
27 Correct 40 ms 115548 KB ok
28 Correct 39 ms 115540 KB ok
29 Correct 39 ms 115544 KB ok
30 Correct 2158 ms 376852 KB ok
31 Correct 1905 ms 303488 KB ok
32 Correct 1262 ms 232388 KB ok
33 Correct 982 ms 216132 KB ok
34 Correct 1290 ms 270752 KB ok
35 Correct 2197 ms 382292 KB ok
36 Correct 1050 ms 239092 KB ok
37 Correct 1510 ms 279420 KB ok
38 Correct 1453 ms 266096 KB ok
39 Correct 1603 ms 316888 KB ok
40 Execution timed out 4610 ms 883408 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 115292 KB ok
2 Correct 37 ms 115284 KB ok
3 Correct 37 ms 115292 KB ok
4 Correct 49 ms 117332 KB ok
5 Correct 52 ms 119384 KB ok
6 Correct 39 ms 115292 KB ok
7 Correct 38 ms 115320 KB ok
8 Runtime error 126 ms 233880 KB Execution killed with signal 8
9 Halted 0 ms 0 KB -