oj.uz

Submission #1042889

# Submission time Handle Problem Language Result Execution time Memory
1042889 2024-08-03T14:04:43 Z ZanP Soccer Stadium (IOI23_soccer) C++17
29.5 / 100
 3746 ms 987024 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
struct point{
    int i, j;
    point(){}
    point(int i, int j){
        this->i = i; this->j = j;
    }
};
struct rect{
    point ul, dr;
    rect(){}
    rect(point ul, point dr){this->ul = ul, this->dr = dr;}
};
bool operator==(const point & a, const point & b){return a.i == b.i && a.j == b.j;}
bool operator==(const rect & a, const rect & b){return a.ul == b.ul && a.dr == b.dr;}
bool operator!=(const rect & a, const rect & b){return !(a.ul == b.ul && a.dr == b.dr);}
bool operator<(const rect & a, const rect & b){
    int h_a = a.dr.i - a.ul.i + 1, h_b = b.dr.i - b.ul.i + 1;
    if(h_a == h_b){
        if(a.ul.j == b.ul.j){
            return a.ul.i < b.ul.i;
        }
        return a.ul.j < b.ul.j;
    }
    return h_a < h_b;
}
 
ostream& operator<<(ostream& os, vector<int> & a){
    os << "{ ";
    for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
    os << "}\n";
    return os;
}
ostream& operator<<(ostream& os, vector<vector<int>> & a){
    os << "{ ";
    for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
    os << "}\n";
    return os;
}
ostream& operator<<(ostream& os, point & a){
    os << "(" << a.i << "," << a.j << ")";
    return os;
}
 
ostream& operator<<(ostream& os, rect & a){
    os << "{" << a.ul << "," << a.dr << "}";
    return os;
}
ostream& operator<<(ostream& os, vector<rect> & a){
    os << "{ ";
    for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
    os << "}\n";
    return os;
}
 
 
vector<vector<int>> look_up, look_down, look_right, look_left;
vector<int> lg;
vector<vector<vector<int>>> rmq_up, rmq_down;
 
int get_rmq_up(int i, int l, int r){
    int k = lg[r - l + 1];
    return min(rmq_up[i][l][k], rmq_up[i][r - (1 << k) + 1][k]);
}
 
int get_rmq_down(int i, int l, int r){
    int k = lg[r - l + 1];
    return min(rmq_down[i][l][k], rmq_down[i][r - (1 << k) + 1][k]);
}
bool already_did = false;
int biggest_stadium(int n, vector<vector<int>> grid)
{
    look_up.clear(); look_down.clear(); look_right.clear(); look_left.clear();
    lg.clear(); rmq_down.clear(); rmq_up.clear();
    look_up.resize(n,vector<int>(n));
    look_down.resize(n,vector<int>(n));
    look_right.resize(n,vector<int>(n));
    look_left.resize(n,vector<int>(n));
    for(int j = 0;j<n;j++){
        look_up[0][j] = 1 - grid[0][j];
        look_down[n-1][j] = 1 - grid[n-1][j];
        look_left[j][0] = 1 - grid[j][0];
        look_right[j][n-1] = 1 - grid[j][n-1];
    }
 
    for(int i = 1; i < n; i++){
        for(int j = 0;j < n; j++){
            look_up[i][j] = (grid[i][j]) ? 0 : 1 + look_up[i-1][j];
            look_down[n-i-1][j] = (grid[n-i-1][j]) ? 0 : 1 + look_down[n-i][j];
            look_left[j][i] = (grid[j][i]) ? 0 : 1 + look_left[j][i-1];
            look_right[j][n-i-1] = (grid[j][n-i-1]) ? 0 : 1 + look_right[j][n-i];
        }
    }
 
    lg.resize(n+1,0);
    for(int i = 2; i<=n;i++){lg[i] = 1 + lg[i>>1];}
 
    //cout << look_up << '\n' << look_down << '\n' << look_right << '\n' << look_left << '\n';
 
    rmq_up.resize(n,vector<vector<int>>(n,vector<int>(lg[n]+1)));
    rmq_down.resize(n,vector<vector<int>>(n,vector<int>(lg[n]+1)));
    for(int i = 0;i<n;i++)for(int j = 0;j<n;j++){
        rmq_up[i][j][0] = look_up[i][j];
        rmq_down[i][j][0] = look_down[i][j];
    }
 
    for(int k = 1; k <= lg[n]; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j + (1 << (k-1)) < n; j++){
                rmq_up[i][j][k] = min(rmq_up[i][j][k-1], rmq_up[i][j + (1 << (k-1))][k-1]);
                rmq_down[i][j][k] = min(rmq_down[i][j][k-1], rmq_down[i][j + (1 << (k-1))][k-1]);
            }
        }
    }
 
    map<rect,int> rect_s;
 
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(grid[i][j])continue;
            int l = j - look_left[i][j] + 1, r = j + look_right[i][j] - 1;
            int up = i - get_rmq_up(i,l,r) + 1, down = i + get_rmq_down(i,l,r) - 1;
            rect R = rect(point(up,l), point(down,r));
            //cout << R << " : (" << rect_s.count(R) << ") " << rect_s[R] << '\n';
            rect_s[R] = rect_s.size();
        }
    }
 
    //cout << "rects:\n";
    int xx = 0;
    int m = rect_s.size();
    vector<rect> rects(m);
    for(pair<const rect, int> & p : rect_s){
        p.second = xx;
        rect a = p.first;
        rects[xx] = a;
        xx++;
    }
    //cout << rects << '\n';
 
    vector<vector<int>> pov(m);
    for(int i = 0;i<m;i++){
        rect a = rects[i];
        if(a.ul.i > 0){
            for(int l = a.ul.j, r = l; l<=a.dr.j;l=r+1){
                int i_i = a.ul.i-1;
                if(grid[i_i][l]){r = l;continue;}
                r = min(l + look_right[i_i][l] - 1, a.dr.j);
                int up = i_i - get_rmq_up(i_i,l,r) + 1, down = i_i + get_rmq_down(i_i,l,r) - 1;
                rect R = rect(point(up,l), point(down,r));
                if(rect_s.count(R))pov[i].push_back(rect_s[R]);
            }
        }
        if(a.dr.i < n-1){
            for(int l = a.ul.j, r = l; l<=a.dr.j;l=r+1){
                int i_i = a.dr.i+1;
                if(grid[i_i][l]){r = l; continue;}
                r = min(l + look_right[i_i][l] - 1, a.dr.j);
                int up = i_i - get_rmq_up(i_i,l,r) + 1, down = i_i + get_rmq_down(i_i,l,r) - 1;
                rect R = rect(point(up,l), point(down,r));
                if(rect_s.count(R))pov[i].push_back(rect_s[R]);
            }
        }
    }
    
    //cout << pov << '\n';
 
    vector<int> dp(m,0);
    int ans = 0;
    for(int i = 0; i < m; i++)
    {
        rect a = rects[i];
        int S = (a.dr.i - a.ul.i + 1) * (a.dr.j - a.ul.j + 1);
        S = max(S,dp[i]);
        dp[i] = S;
        for(int & b_i : pov[i]){
            rect b = rects[b_i];
            int Sb = (b.dr.i - b.ul.i - a.dr.i + a.ul.i) * (b.dr.j - b.ul.j + 1);
            dp[b_i] = max(Sb + S, dp[b_i]);
        }
        ans = max(ans, dp[i]);
    }
    //cout << dp << '\n';
    if(already_did){return ans;}
    vector<vector<int>> transpose(n,vector<int>(n));
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            transpose[i][j] = grid[j][i];
        }
    }
    already_did = true;
    return max(ans, biggest_stadium(n,transpose));
}
 
// int main(){
//      cout << 
//      biggest_stadium(5, {{0, 0, 0, 1, 0},
//                          {1, 0, 1, 0, 0},
//                          {0, 0, 0, 0, 0},
//                          {1, 0, 0, 0, 0},
//                          {0, 1, 0, 1, 0}}) << '\n';
//  }

Compilation message

soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
soccer.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
      |                    ~^~~~~~~~~
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::vector<int> >&)':
soccer.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
      |                    ~^~~~~~~~~
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<rect>&)':
soccer.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
      |                    ~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 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 3 ms 2140 KB ok
8 Correct 87 ms 44220 KB ok
9 Correct 1558 ms 821756 KB ok

Subtask #2
2.0 / 8.0

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

Subtask #3
5.5 / 22.0

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

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 360 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 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Partially correct 0 ms 348 KB partial
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 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Partially correct 0 ms 348 KB partial
29 Partially correct 1 ms 348 KB partial
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 0 ms 344 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Partially correct 0 ms 348 KB partial

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 360 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 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Partially correct 0 ms 348 KB partial
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 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Partially correct 0 ms 348 KB partial
29 Partially correct 1 ms 348 KB partial
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 0 ms 344 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Partially correct 0 ms 348 KB partial
42 Partially correct 164 ms 49660 KB partial
43 Partially correct 199 ms 53588 KB partial
44 Partially correct 104 ms 44876 KB partial
45 Partially correct 103 ms 44376 KB partial
46 Partially correct 131 ms 46888 KB partial
47 Partially correct 88 ms 44112 KB partial
48 Correct 89 ms 44156 KB ok
49 Partially correct 88 ms 44256 KB partial
50 Correct 104 ms 45144 KB ok
51 Correct 115 ms 48216 KB ok
52 Partially correct 77 ms 44128 KB partial
53 Partially correct 75 ms 44120 KB partial
54 Partially correct 76 ms 44236 KB partial
55 Partially correct 78 ms 44112 KB partial
56 Correct 76 ms 44112 KB ok
57 Partially correct 96 ms 44372 KB partial
58 Partially correct 100 ms 44368 KB partial
59 Partially correct 97 ms 44368 KB partial

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 360 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 3 ms 2140 KB ok
9 Correct 87 ms 44220 KB ok
10 Correct 1558 ms 821756 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 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 1 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Partially correct 0 ms 348 KB partial
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 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 0 ms 344 KB ok
32 Correct 0 ms 348 KB ok
33 Partially correct 0 ms 348 KB partial
34 Partially correct 1 ms 348 KB partial
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 0 ms 344 KB ok
44 Correct 0 ms 348 KB ok
45 Correct 0 ms 348 KB ok
46 Partially correct 0 ms 348 KB partial
47 Partially correct 164 ms 49660 KB partial
48 Partially correct 199 ms 53588 KB partial
49 Partially correct 104 ms 44876 KB partial
50 Partially correct 103 ms 44376 KB partial
51 Partially correct 131 ms 46888 KB partial
52 Partially correct 88 ms 44112 KB partial
53 Correct 89 ms 44156 KB ok
54 Partially correct 88 ms 44256 KB partial
55 Correct 104 ms 45144 KB ok
56 Correct 115 ms 48216 KB ok
57 Partially correct 77 ms 44128 KB partial
58 Partially correct 75 ms 44120 KB partial
59 Partially correct 76 ms 44236 KB partial
60 Partially correct 78 ms 44112 KB partial
61 Correct 76 ms 44112 KB ok
62 Partially correct 96 ms 44372 KB partial
63 Partially correct 100 ms 44368 KB partial
64 Partially correct 97 ms 44368 KB partial
65 Partially correct 3746 ms 912132 KB partial
66 Correct 3185 ms 987024 KB ok
67 Correct 2160 ms 894348 KB ok
68 Partially correct 1929 ms 824456 KB partial
69 Partially correct 2165 ms 833276 KB partial
70 Partially correct 2428 ms 845140 KB partial
71 Partially correct 1877 ms 823888 KB partial
72 Partially correct 1693 ms 823320 KB partial
73 Correct 1657 ms 823380 KB ok
74 Correct 1680 ms 823380 KB ok
75 Correct 1658 ms 823428 KB ok
76 Correct 2115 ms 839544 KB ok
77 Correct 2073 ms 839424 KB ok
78 Partially correct 2235 ms 861524 KB partial
79 Correct 1680 ms 838484 KB ok
80 Partially correct 1648 ms 833676 KB partial
81 Partially correct 1848 ms 830972 KB partial
82 Partially correct 1755 ms 835068 KB partial
83 Partially correct 2460 ms 884300 KB partial
84 Partially correct 1612 ms 823292 KB partial
85 Partially correct 1518 ms 823500 KB partial
86 Partially correct 1684 ms 823300 KB partial
87 Partially correct 1666 ms 823488 KB partial
88 Correct 1744 ms 823672 KB ok
89 Partially correct 1943 ms 823392 KB partial
90 Partially correct 1751 ms 823328 KB partial
91 Partially correct 1740 ms 823440 KB partial
92 Correct 2196 ms 860924 KB ok
93 Correct 2287 ms 872852 KB ok
94 Correct 1936 ms 838656 KB ok
95 Correct 1777 ms 831396 KB ok
96 Correct 1792 ms 828756 KB ok
97 Correct 1701 ms 827132 KB ok
98 Correct 1670 ms 824912 KB ok
99 Correct 2480 ms 868144 KB ok
100 Partially correct 1966 ms 824156 KB partial
101 Partially correct 2027 ms 823892 KB partial
102 Partially correct 2075 ms 824056 KB partial
103 Partially correct 1891 ms 824080 KB partial
104 Partially correct 1924 ms 824148 KB partial
105 Partially correct 2076 ms 824196 KB partial
106 Partially correct 2040 ms 824316 KB partial
107 Correct 1882 ms 824144 KB ok
108 Correct 2153 ms 832084 KB ok
109 Correct 2149 ms 830716 KB ok