제출 #916617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916617		abcvuitunggio	축구 경기장 (IOI23_soccer)	C++17	30 / 100	4610 ms	883408 KiB

soccer

#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
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30