oj.uz

Submission #916621

# Submission time Handle Problem Language Result Execution time Memory
916621 2024-01-26T07:24:17 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 942700 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=32,inf=1e9;
int n,res;
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 (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 35 ms 98904 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 98928 KB ok
2 Correct 29 ms 98908 KB ok
3 Correct 41 ms 101272 KB ok
4 Correct 43 ms 103280 KB ok
5 Correct 29 ms 98704 KB ok
6 Correct 29 ms 98852 KB ok
7 Runtime error 108 ms 200620 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 98928 KB ok
2 Correct 29 ms 98908 KB ok
3 Correct 30 ms 98760 KB ok
4 Correct 27 ms 98944 KB ok
5 Correct 28 ms 98756 KB ok
6 Correct 31 ms 98908 KB ok
7 Correct 20 ms 98908 KB ok
8 Correct 29 ms 98840 KB ok
9 Correct 29 ms 98908 KB ok
10 Correct 27 ms 98744 KB ok
11 Correct 34 ms 98772 KB ok
12 Correct 30 ms 98908 KB ok
13 Correct 30 ms 98908 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98904 KB ok
2 Correct 27 ms 98928 KB ok
3 Correct 29 ms 98908 KB ok
4 Correct 30 ms 98760 KB ok
5 Correct 27 ms 98944 KB ok
6 Correct 28 ms 98756 KB ok
7 Correct 31 ms 98908 KB ok
8 Correct 20 ms 98908 KB ok
9 Correct 29 ms 98840 KB ok
10 Correct 29 ms 98908 KB ok
11 Correct 27 ms 98744 KB ok
12 Correct 34 ms 98772 KB ok
13 Correct 30 ms 98908 KB ok
14 Correct 30 ms 98908 KB ok
15 Correct 32 ms 99420 KB ok
16 Correct 33 ms 99220 KB ok
17 Correct 30 ms 99000 KB ok
18 Correct 28 ms 98936 KB ok
19 Correct 29 ms 98908 KB ok
20 Correct 28 ms 98904 KB ok
21 Correct 28 ms 98908 KB ok
22 Correct 28 ms 98908 KB ok
23 Correct 31 ms 98908 KB ok
24 Correct 28 ms 98908 KB ok
25 Correct 31 ms 99004 KB ok
26 Correct 28 ms 99164 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98904 KB ok
2 Correct 27 ms 98928 KB ok
3 Correct 29 ms 98908 KB ok
4 Correct 41 ms 101272 KB ok
5 Correct 43 ms 103280 KB ok
6 Correct 30 ms 98760 KB ok
7 Correct 27 ms 98944 KB ok
8 Correct 28 ms 98756 KB ok
9 Correct 31 ms 98908 KB ok
10 Correct 20 ms 98908 KB ok
11 Correct 29 ms 98840 KB ok
12 Correct 29 ms 98908 KB ok
13 Correct 27 ms 98744 KB ok
14 Correct 34 ms 98772 KB ok
15 Correct 30 ms 98908 KB ok
16 Correct 30 ms 98908 KB ok
17 Correct 32 ms 99420 KB ok
18 Correct 33 ms 99220 KB ok
19 Correct 30 ms 99000 KB ok
20 Correct 28 ms 98936 KB ok
21 Correct 29 ms 98908 KB ok
22 Correct 28 ms 98904 KB ok
23 Correct 28 ms 98908 KB ok
24 Correct 28 ms 98908 KB ok
25 Correct 31 ms 98908 KB ok
26 Correct 28 ms 98908 KB ok
27 Correct 31 ms 99004 KB ok
28 Correct 28 ms 99164 KB ok
29 Correct 32 ms 99072 KB ok
30 Correct 2664 ms 382484 KB ok
31 Correct 1885 ms 299716 KB ok
32 Correct 1138 ms 227120 KB ok
33 Correct 995 ms 213328 KB ok
34 Correct 1445 ms 262224 KB ok
35 Correct 2333 ms 390924 KB ok
36 Correct 1149 ms 238560 KB ok
37 Correct 1328 ms 279220 KB ok
38 Correct 1384 ms 267344 KB ok
39 Correct 1734 ms 318812 KB ok
40 Execution timed out 4579 ms 942700 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98904 KB ok
2 Correct 27 ms 98928 KB ok
3 Correct 29 ms 98908 KB ok
4 Correct 41 ms 101272 KB ok
5 Correct 43 ms 103280 KB ok
6 Correct 30 ms 98760 KB ok
7 Correct 27 ms 98944 KB ok
8 Correct 28 ms 98756 KB ok
9 Correct 31 ms 98908 KB ok
10 Correct 20 ms 98908 KB ok
11 Correct 29 ms 98840 KB ok
12 Correct 29 ms 98908 KB ok
13 Correct 27 ms 98744 KB ok
14 Correct 34 ms 98772 KB ok
15 Correct 30 ms 98908 KB ok
16 Correct 30 ms 98908 KB ok
17 Correct 32 ms 99420 KB ok
18 Correct 33 ms 99220 KB ok
19 Correct 30 ms 99000 KB ok
20 Correct 28 ms 98936 KB ok
21 Correct 29 ms 98908 KB ok
22 Correct 28 ms 98904 KB ok
23 Correct 28 ms 98908 KB ok
24 Correct 28 ms 98908 KB ok
25 Correct 31 ms 98908 KB ok
26 Correct 28 ms 98908 KB ok
27 Correct 31 ms 99004 KB ok
28 Correct 28 ms 99164 KB ok
29 Correct 32 ms 99072 KB ok
30 Correct 2664 ms 382484 KB ok
31 Correct 1885 ms 299716 KB ok
32 Correct 1138 ms 227120 KB ok
33 Correct 995 ms 213328 KB ok
34 Correct 1445 ms 262224 KB ok
35 Correct 2333 ms 390924 KB ok
36 Correct 1149 ms 238560 KB ok
37 Correct 1328 ms 279220 KB ok
38 Correct 1384 ms 267344 KB ok
39 Correct 1734 ms 318812 KB ok
40 Execution timed out 4579 ms 942700 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98904 KB ok
2 Correct 27 ms 98928 KB ok
3 Correct 29 ms 98908 KB ok
4 Correct 41 ms 101272 KB ok
5 Correct 43 ms 103280 KB ok
6 Correct 29 ms 98704 KB ok
7 Correct 29 ms 98852 KB ok
8 Runtime error 108 ms 200620 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -