oj.uz

Submission #1072517

# Submission time Handle Problem Language Result Execution time Memory
1072517 2024-08-23T21:06:36 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
0 / 100
 970 ms 2097152 KB 
#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)));

    int dp[32][32][32][32][32][32] = { };

    auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int 
    {
        if(dp[i][j][a][b][c][d] != 0) return dp[i][j][a][b][c][d];
        dp[i][j][a][b][c][d] = (b - a + 1); 
        if(i != j) dp[i][j][a][b][c][d] += (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[i][j][a][b][c][d] = (dp[i][j][a][b][c][d] + 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 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 963 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 970 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 970 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 963 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 963 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 963 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 963 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -