oj.uz

Submission #1011315

# Submission time Handle Problem Language Result Execution time Memory
1011315 2024-06-30T10:18:47 Z boris_mihov Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2367 ms 154708 KB 
#include "soccer.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 2000 + 10;
const int INF  = 1e9;

int n;
int p[MAXN][MAXN];
int t[MAXN][MAXN];

inline int sum(int rowB, int colB, int rowE, int colE)
{
    return p[rowE][colE] - p[rowB - 1][colE] - p[rowE][colB - 1] + p[rowB - 1][colB - 1];
}

std::pair <int,int> extend(int row, int colB, int colE)
{
    assert(row > 0);
    std::pair <int,int> sol;
    int l = 0, r = row, mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (sum(mid, colB, row, colE) != 0) l = mid;
        else r = mid;
    }

    sol.first = r;
    l = row, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (sum(row, colB, mid, colE) == 0) l = mid;
        else r = mid;
    }

    sol.second = l;
    return sol;
}

std::vector <std::pair <int,int>> split(int row, int colB, int colE)
{
    int last = colB;
    std::vector <std::pair <int,int>> sol;
    for (int i = colB ; i <= colE ; ++i)
    {
        if (t[row][i])
        {
            if (last < i)
            {
                sol.push_back({last, i - 1});
            }

            last = i + 1;
        }
    }

    if (last <= colE) sol.push_back({last, colE});
    return sol;
}

std::map <std::array <int,4>, int> dp;
int f(int rowB, int colB, int rowE, int colE)
{
    if (colB > colE)
    {
        return 0;
    }

    if (rowB == 1 && rowE == n)
    {
        return 0;
    }
    
    if (dp.count({rowB, colB, rowE, colE}))
    {
        return dp[{rowB, colB, rowE, colE}];
    }

    int res = 0;
    if (rowB > 1)
    {
        std::vector <std::pair <int,int>> v = split(rowB - 1, colB, colE);
        for (const auto &[nextColB, nextColE] : v)
        {
            int lastRes = res;
            auto [nextRowB, nextRowE] = extend(rowB - 1, nextColB, nextColE);
            res = std::max(res, (nextColE - nextColB + 1) * (nextRowE - nextRowB + 1 - (rowE - rowB + 1)) + f(nextRowB, nextColB, nextRowE, nextColE));
        }
    }

    if (rowE < n)
    {
        std::vector <std::pair <int,int>> v = split(rowE + 1, colB, colE);
        for (const auto &[nextColB, nextColE] : v)
        {
            int lastRes = res;
            auto [nextRowB, nextRowE] = extend(rowE + 1, nextColB, nextColE);
            res = std::max(res, (nextColE - nextColB + 1) * (nextRowE - nextRowB + 1 - (rowE - rowB + 1)) + f(nextRowB, nextColB, nextRowE, nextColE));
        }
    }

    return dp[{rowB, colB, rowE, colE}] = res;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n = N;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            t[i][j] = F[i - 1][j - 1];
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + t[i][j];        
        }
    }

    int max = 0;
    for (int row = 1 ; row <= n ; ++row)
    {
        std::vector <std::pair <int,int>> v = split(row, 1, n);
        for (const auto &[colB, colE] : v)
        {
            auto [rowB, rowE] = extend(row, colB, colE);
            max = std::max(max, f(rowB, colB, rowE, colE) + (rowE - rowB + 1) * (colE - colB + 1));
        }
    }

    return max;
}

Compilation message

soccer.cpp: In function 'std::pair<int, int> extend(int, int, int)':
soccer.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         mid = l + r >> 1;
      |               ~~^~~
soccer.cpp:35:28: warning: right operand of comma operator has no effect [-Wunused-value]
   35 |     l = row, r = n + 1, mid;
      |                            ^
soccer.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         mid = l + r >> 1;
      |               ~~^~~
soccer.cpp: In function 'int f(int, int, int, int)':
soccer.cpp:92:17: warning: unused variable 'lastRes' [-Wunused-variable]
   92 |             int lastRes = res;
      |                 ^~~~~~~
soccer.cpp:103:17: warning: unused variable 'lastRes' [-Wunused-variable]
  103 |             int lastRes = res;
      |                 ^~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 1224 KB ok
8 Correct 15 ms 8792 KB ok
9 Correct 217 ms 70928 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 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 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 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 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 344 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 344 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 616 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 0 ms 600 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 0 ms 604 KB ok
37 Correct 0 ms 700 KB ok
38 Correct 0 ms 604 KB ok
39 Correct 0 ms 696 KB ok
40 Correct 0 ms 604 KB ok
41 Correct 1 ms 604 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 344 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 616 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 0 ms 600 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 0 ms 604 KB ok
37 Correct 0 ms 700 KB ok
38 Correct 0 ms 604 KB ok
39 Correct 0 ms 696 KB ok
40 Correct 0 ms 604 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 57 ms 11860 KB ok
43 Correct 64 ms 12792 KB ok
44 Correct 28 ms 9560 KB ok
45 Correct 24 ms 9296 KB ok
46 Correct 51 ms 10796 KB ok
47 Correct 18 ms 8716 KB ok
48 Correct 17 ms 8796 KB ok
49 Correct 15 ms 8796 KB ok
50 Correct 22 ms 8792 KB ok
51 Correct 22 ms 9968 KB ok
52 Correct 15 ms 8796 KB ok
53 Correct 15 ms 8792 KB ok
54 Correct 17 ms 8840 KB ok
55 Correct 15 ms 8796 KB ok
56 Correct 15 ms 8788 KB ok
57 Correct 80 ms 12656 KB ok
58 Correct 71 ms 13252 KB ok
59 Correct 76 ms 13908 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 1224 KB ok
9 Correct 15 ms 8792 KB ok
10 Correct 217 ms 70928 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 344 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 604 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 616 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 0 ms 600 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 0 ms 604 KB ok
42 Correct 0 ms 700 KB ok
43 Correct 0 ms 604 KB ok
44 Correct 0 ms 696 KB ok
45 Correct 0 ms 604 KB ok
46 Correct 1 ms 604 KB ok
47 Correct 57 ms 11860 KB ok
48 Correct 64 ms 12792 KB ok
49 Correct 28 ms 9560 KB ok
50 Correct 24 ms 9296 KB ok
51 Correct 51 ms 10796 KB ok
52 Correct 18 ms 8716 KB ok
53 Correct 17 ms 8796 KB ok
54 Correct 15 ms 8796 KB ok
55 Correct 22 ms 8792 KB ok
56 Correct 22 ms 9968 KB ok
57 Correct 15 ms 8796 KB ok
58 Correct 15 ms 8792 KB ok
59 Correct 17 ms 8840 KB ok
60 Correct 15 ms 8796 KB ok
61 Correct 15 ms 8788 KB ok
62 Correct 80 ms 12656 KB ok
63 Correct 71 ms 13252 KB ok
64 Correct 76 ms 13908 KB ok
65 Correct 1086 ms 121876 KB ok
66 Correct 559 ms 118100 KB ok
67 Correct 339 ms 92048 KB ok
68 Correct 266 ms 73552 KB ok
69 Correct 518 ms 85000 KB ok
70 Correct 735 ms 94992 KB ok
71 Correct 243 ms 72528 KB ok
72 Correct 241 ms 71056 KB ok
73 Correct 206 ms 71224 KB ok
74 Correct 217 ms 70992 KB ok
75 Correct 236 ms 70996 KB ok
76 Correct 333 ms 71252 KB ok
77 Correct 349 ms 71196 KB ok
78 Correct 310 ms 81292 KB ok
79 Correct 284 ms 75420 KB ok
80 Correct 260 ms 73872 KB ok
81 Correct 278 ms 74064 KB ok
82 Correct 289 ms 77984 KB ok
83 Correct 388 ms 89996 KB ok
84 Correct 212 ms 71184 KB ok
85 Correct 199 ms 70992 KB ok
86 Correct 210 ms 71252 KB ok
87 Correct 220 ms 72208 KB ok
88 Correct 218 ms 71252 KB ok
89 Correct 211 ms 71192 KB ok
90 Correct 221 ms 71052 KB ok
91 Correct 222 ms 71072 KB ok
92 Correct 289 ms 82844 KB ok
93 Correct 304 ms 84816 KB ok
94 Correct 254 ms 75600 KB ok
95 Correct 225 ms 73300 KB ok
96 Correct 206 ms 72784 KB ok
97 Correct 195 ms 72276 KB ok
98 Correct 207 ms 71760 KB ok
99 Correct 853 ms 136528 KB ok
100 Correct 2059 ms 134236 KB ok
101 Correct 1939 ms 128024 KB ok
102 Correct 2007 ms 134224 KB ok
103 Correct 2206 ms 144828 KB ok
104 Correct 2301 ms 148728 KB ok
105 Correct 2367 ms 151668 KB ok
106 Correct 2231 ms 154708 KB ok
107 Correct 2152 ms 154200 KB ok
108 Correct 323 ms 76264 KB ok
109 Correct 311 ms 76184 KB ok