oj.uz

Submission #844638

# Submission time Handle Problem Language Result Execution time Memory
844638 2023-09-05T15:15:08 Z Sorting Soccer Stadium (IOI23_soccer) C++17
0 / 100
 5 ms 1116 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 7;

bool f[N][N];
int prefix[N][N];
int n;

pair<int, bool> dp[N][N][N][N][N][N];

bool bad(int l1, int r1, int l2, int r2){
    if(l1 <= l2 && r2 <= r1)
        return false;
    if(l2 <= l1 && r1 <= r2)
        return false;
    return true;
}

int solve(int i1, int i2, int l1, int r1, int l2, int r2){
    auto &[ans, solved] = dp[i1][i2][l1][r1][l2][r2];
    if(solved)
        return ans;

    solved = true;
    ans = 0;

    if(r1 - l1 >= r2 - l2 && i1 != 0){
        for(int l3 = 0; l3 < n; ++l3){
            for(int r3 = l3; r3 < n; ++r3){
                if(f[i1 - 1][r3])
                    break;

                if(bad(l3, r3, l1, r1))
                    continue;
                if(bad(l3, r3, l2, r2))
                    continue;
                if(r3 - l3 > r1 - l1)
                    continue;

                ans = max(ans, solve(i1 - 1, i2, l3, r3, l2, r2) + r3 - l3 + 1);
            }
        }
    }
    if(r2 - l2 >= r1 - l1 && i2 != n - 1){
        for(int l3 = 0; l3 < n; ++l3){
            for(int r3 = l3; r3 < n; ++r3){
                if(f[i2 + 1][r3])
                    break;

                if(bad(l3, r3, l1, r1))
                    continue;
                if(bad(l3, r3, l2, r2))
                    continue;
                if(r3 - l3 > r2 - l2)
                    continue;

                ans = max(ans, solve(i1, i2 + 1, l1, r1, l3, r3) + r3 - l3 + 1);
            }
        }
    }

    return ans;
}

int biggest_stadium(int _N, std::vector<std::vector<int>> F){
    n = _N;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            f[i][j] = F[i][j];

    int ans = 0;
    for(int i = 0; i < n; ++i){
        for(int l = 0; l < n; ++l){
            for(int r = l; r < n; ++r){
                if(f[i][r])
                    break;
               ans = max(ans, solve(i, i, l, r, l, r) + r - l + 1);
            }
        }
    }

    return ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Incorrect 5 ms 1116 KB wrong
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 0 ms 348 KB partial
4 Partially correct 0 ms 348 KB partial
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 348 KB partial
7 Correct 0 ms 348 KB ok
8 Incorrect 0 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 0 ms 348 KB partial
5 Partially correct 0 ms 348 KB partial
6 Correct 0 ms 348 KB ok
7 Partially correct 0 ms 348 KB partial
8 Correct 0 ms 348 KB ok
9 Incorrect 0 ms 348 KB wrong
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 5 ms 1116 KB wrong
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 5 ms 1116 KB wrong
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 5 ms 1116 KB wrong
5 Halted 0 ms 0 KB -