Submission #1072518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072518		HorizonWest	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4563 ms	334040 KiB

soccer

#include "soccer.h"
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
using namespace std;

int biggest_stadium(int n, std::vector<std::vector<int>> f)
{
    vector <vector<int>> A(n, vector <int> (n, 0)),
        B(n, vector <int> (n, 0)); 

    for(int i = 0; i < n; i++){
        int last = -1; 
        for(int j = 0; j < n; j++){
            if(f[i][j] == 1) last = j; 
            A[i][j] = last;
        }   

        last = n;
        for(int j = n-1; j >= 0; j--){
            if(f[i][j] == 1) last = j; 
            B[i][j] = last;
        }     
    }

    //vector <vector<vector<int>>> dp1(n + 1, vector <vector<int>> 
    //    (n + 1, vector <int> (n + 1, -1)));

    //vector <vector<vector<int>>> dp2(n + 1, vector <vector<int>> 
    //    (n + 1, vector <int> (n + 1, -1)));

    map <vector<int>, int> dp;

    auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int 
    {
        vector <int> x = { i, j, a, b, c, d };
        if(dp[x] != 0) return dp[x];
        dp[x] = (b - a + 1); 
        if(i != j) dp[x] += (d - c + 1);

        int mx = 0;

        if(i != 0)
        {
            for(int k = a; k <= b; k++) if(f[i-1][k] == 0)
            {
                int l1 = max(A[i-1][k]+1, a), r1 = min(B[i-1][k]-1, b);
                int l2 = max(c, l1), r2 =  min(d, r1);
                mx = max(mx, F(F, i-1, j, l1, r1, l2, r2) - (r2 - l2 + 1));
            }
        }

        if(j != n-1)
        {
            for(int k = c; k <= d; k++) if(f[j+1][k] == 0)
            {
                int l2 = max(A[j+1][k]+1, c), r2 = min(B[j+1][k]-1, d);
                int l1 = max(a, l2), r1 =  min(b, r2);
                mx = max(mx, F(F, i, j+1, l1, r1, l2, r2) - (r1 - l1 + 1));
            }
        }

        return dp[x] = (dp[x] + mx);
    };      
    

    
    int ans = 0; 

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int l = A[i][j]+1, r = B[i][j]-1;

            ans = max(ans, F(F, i, i, l, r, l, r));
        }
    }

    return ans;
}

• 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