Submission #1220826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220826		HappyCapybara	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4596 ms	915732 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int N;
vector<vector<int>> F;

unordered_map<ll,int> dp;

ll h(ll t, ll b, ll l, ll r){
    return t*pow(2000, 3)+b*pow(2000, 2)+l*2000+r;
}

int solve(int t, int tl, int tr, int b, int bl, int br){
    int l = max(tl, bl), r = min(tr, br);
    if (tl == -1 || bl == -1) return -pow(10, 9);
    if (dp.find(h(t, b, l, r)) != dp.end()) return dp[h(t, b, l, r)];
    int res = 0;
    if (t > 0){
        int l = -1;
        for (int j=max(tl, bl); j<=min(tr, br)+1; j++){
            if (j == min(tr, br)+1 || F[t-1][j]){
                res = max(res, j-l+solve(t-1, l, j-1, b, bl, br));
                l = -1;
            }
            else if (l == -1) l = j;
        }
    }
    if (b < N-1){
        int l = -1;
        for (int j=max(tl, bl); j<=min(tr, br)+1; j++){
            if (j == min(tr, br)+1 || F[b+1][j]){
                res = max(res, j-l+solve(t, tl, tr, b+1, l, j-1));
                l = -1;
            }
            else if (l == -1) l = j;
        }
    }
    return dp[h(t, b, l, r)] = res;
}

int biggest_stadium(int N, vector<vector<int>> F){
    ::N = N;
    ::F = F;
    int res = 0;
    for (int i=0; i<N; i++){
        int l = -1;
        for (int j=0; j<=N; j++){
            if (j == N || F[i][j]){
                res = max(res, j-l+solve(i, l, j-1, i, l, j-1));
                l = -1;
            }
            else if (l == -1) l = j;
        }
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30