oj.uz

Submission #916610

# Submission time Handle Problem Language Result Execution time Memory
916610 2024-01-26T07:08:29 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
0 / 100
 156 ms 233964 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);
    }
    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 115292 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 115140 KB ok
2 Correct 35 ms 115284 KB ok
3 Correct 55 ms 119120 KB ok
4 Correct 68 ms 122964 KB ok
5 Correct 35 ms 115536 KB ok
6 Correct 35 ms 115164 KB ok
7 Runtime error 156 ms 233964 KB Execution killed with signal 8
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 115140 KB ok
2 Correct 35 ms 115284 KB ok
3 Correct 36 ms 115352 KB ok
4 Correct 35 ms 115288 KB ok
5 Correct 35 ms 115288 KB ok
6 Correct 35 ms 115280 KB ok
7 Incorrect 35 ms 115280 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115292 KB ok
2 Correct 35 ms 115140 KB ok
3 Correct 35 ms 115284 KB ok
4 Correct 36 ms 115352 KB ok
5 Correct 35 ms 115288 KB ok
6 Correct 35 ms 115288 KB ok
7 Correct 35 ms 115280 KB ok
8 Incorrect 35 ms 115280 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115292 KB ok
2 Correct 35 ms 115140 KB ok
3 Correct 35 ms 115284 KB ok
4 Correct 55 ms 119120 KB ok
5 Correct 68 ms 122964 KB ok
6 Correct 36 ms 115352 KB ok
7 Correct 35 ms 115288 KB ok
8 Correct 35 ms 115288 KB ok
9 Correct 35 ms 115280 KB ok
10 Incorrect 35 ms 115280 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115292 KB ok
2 Correct 35 ms 115140 KB ok
3 Correct 35 ms 115284 KB ok
4 Correct 55 ms 119120 KB ok
5 Correct 68 ms 122964 KB ok
6 Correct 36 ms 115352 KB ok
7 Correct 35 ms 115288 KB ok
8 Correct 35 ms 115288 KB ok
9 Correct 35 ms 115280 KB ok
10 Incorrect 35 ms 115280 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 115292 KB ok
2 Correct 35 ms 115140 KB ok
3 Correct 35 ms 115284 KB ok
4 Correct 55 ms 119120 KB ok
5 Correct 68 ms 122964 KB ok
6 Correct 35 ms 115536 KB ok
7 Correct 35 ms 115164 KB ok
8 Runtime error 156 ms 233964 KB Execution killed with signal 8
9 Halted 0 ms 0 KB -