oj.uz

Submission #843401

# Submission time Handle Problem Language Result Execution time Memory
843401 2023-09-04T01:37:06 Z Sorting Soccer Stadium (IOI23_soccer) C++17
8 / 100
 3 ms 1116 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 7 + 3;

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

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

void init_prefix(){
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            prefix[i][j] = !f[i - 1][j - 1];
        }
    }

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            prefix[i][j] += prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
        }
    }
}

int get_sum(int x1, int y1, int x2, int y2){
    if(x1 > x2 || y1 > y2)
        return 0;
    return prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1];
}

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 l1, int r1, int l2, int r2, int i, bool up){
    if(i == n)
        return 0;

    auto &[ans, solved] = dp[l1][r1][l2][r2][i][up];
    if(solved)
        return ans;

    solved = true;
    ans = 0;

    for(int l3 = 0; l3 < n; ++l3){
        for(int r3 = l3; r3 < n; ++r3){
            if(f[i][r3])
                break;

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

            if(!up && (l3 < l2 || r2 < r3))
                continue;

            bool new_up = up;
            if(up && (l2 < l3 || r3 < r2))
                new_up = false;

            int cand = r3 - l3 + 1;
            cand += solve(l1, r1, l3, r3, i + 1, new_up);
            ans = max(ans, cand);
        }
    }

    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];

    init_prefix();

    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(l, r, l, r, i + 1, true) + r - l + 1);
            }
        }
    }

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

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 1 ms 600 KB ok
12 Correct 1 ms 344 KB ok
13 Correct 0 ms 344 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 600 KB ok
13 Correct 1 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 1 ms 600 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 344 KB ok
22 Incorrect 0 ms 548 KB wrong
23 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

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