oj.uz

Submission #1042890

# Submission time Handle Problem Language Result Execution time Memory
1042890 2024-08-03T14:05:42 Z ZanP Soccer Stadium (IOI23_soccer) C++17
29.5 / 100
 4240 ms 987016 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 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 0 ms 604 KB ok
7 Correct 4 ms 2140 KB ok
8 Correct 70 ms 44112 KB ok
9 Correct 1635 ms 818548 KB ok

Subtask #2
2.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 432 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Partially correct 1 ms 344 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 432 KB ok

Subtask #3
5.5 / 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 432 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Partially correct 1 ms 344 KB partial
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 344 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 432 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Partially correct 1 ms 348 KB partial
18 Correct 1 ms 344 KB ok
19 Correct 1 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 444 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 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 432 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Partially correct 1 ms 344 KB partial
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 344 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 432 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Partially correct 1 ms 348 KB partial
20 Correct 1 ms 344 KB ok
21 Correct 1 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 444 KB ok
27 Correct 0 ms 348 KB ok
28 Partially correct 0 ms 348 KB partial
29 Partially correct 0 ms 348 KB partial
30 Correct 0 ms 348 KB ok
31 Correct 1 ms 604 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 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 0 ms 436 KB ok
40 Correct 1 ms 344 KB ok
41 Partially correct 2 ms 344 KB partial

Subtask #5
4.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 432 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Partially correct 1 ms 344 KB partial
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 344 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 432 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Partially correct 1 ms 348 KB partial
20 Correct 1 ms 344 KB ok
21 Correct 1 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 444 KB ok
27 Correct 0 ms 348 KB ok
28 Partially correct 0 ms 348 KB partial
29 Partially correct 0 ms 348 KB partial
30 Correct 0 ms 348 KB ok
31 Correct 1 ms 604 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 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 0 ms 436 KB ok
40 Correct 1 ms 344 KB ok
41 Partially correct 2 ms 344 KB partial
42 Partially correct 204 ms 49780 KB partial
43 Partially correct 230 ms 53584 KB partial
44 Partially correct 96 ms 44800 KB partial
45 Partially correct 118 ms 44372 KB partial
46 Partially correct 130 ms 46932 KB partial
47 Partially correct 70 ms 44112 KB partial
48 Correct 83 ms 43976 KB ok
49 Partially correct 102 ms 44116 KB partial
50 Correct 117 ms 45180 KB ok
51 Correct 113 ms 48076 KB ok
52 Partially correct 63 ms 44220 KB partial
53 Partially correct 63 ms 43976 KB partial
54 Partially correct 66 ms 44116 KB partial
55 Partially correct 67 ms 44084 KB partial
56 Correct 64 ms 44112 KB ok
57 Partially correct 118 ms 44368 KB partial
58 Partially correct 80 ms 44336 KB partial
59 Partially correct 104 ms 44368 KB partial

Subtask #6
7.5 / 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 0 ms 604 KB ok
8 Correct 4 ms 2140 KB ok
9 Correct 70 ms 44112 KB ok
10 Correct 1635 ms 818548 KB ok
11 Correct 0 ms 432 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Partially correct 1 ms 344 KB partial
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 ms 344 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 432 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Partially correct 1 ms 348 KB partial
25 Correct 1 ms 344 KB ok
26 Correct 1 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 444 KB ok
32 Correct 0 ms 348 KB ok
33 Partially correct 0 ms 348 KB partial
34 Partially correct 0 ms 348 KB partial
35 Correct 0 ms 348 KB ok
36 Correct 1 ms 604 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 1 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 1 ms 348 KB ok
43 Correct 1 ms 348 KB ok
44 Correct 0 ms 436 KB ok
45 Correct 1 ms 344 KB ok
46 Partially correct 2 ms 344 KB partial
47 Partially correct 204 ms 49780 KB partial
48 Partially correct 230 ms 53584 KB partial
49 Partially correct 96 ms 44800 KB partial
50 Partially correct 118 ms 44372 KB partial
51 Partially correct 130 ms 46932 KB partial
52 Partially correct 70 ms 44112 KB partial
53 Correct 83 ms 43976 KB ok
54 Partially correct 102 ms 44116 KB partial
55 Correct 117 ms 45180 KB ok
56 Correct 113 ms 48076 KB ok
57 Partially correct 63 ms 44220 KB partial
58 Partially correct 63 ms 43976 KB partial
59 Partially correct 66 ms 44116 KB partial
60 Partially correct 67 ms 44084 KB partial
61 Correct 64 ms 44112 KB ok
62 Partially correct 118 ms 44368 KB partial
63 Partially correct 80 ms 44336 KB partial
64 Partially correct 104 ms 44368 KB partial
65 Partially correct 4240 ms 908168 KB partial
66 Correct 3642 ms 987016 KB ok
67 Correct 2091 ms 894300 KB ok
68 Partially correct 1766 ms 824584 KB partial
69 Partially correct 2078 ms 833364 KB partial
70 Partially correct 2356 ms 845196 KB partial
71 Partially correct 1740 ms 824060 KB partial
72 Partially correct 1545 ms 823288 KB partial
73 Correct 1588 ms 823376 KB ok
74 Correct 1552 ms 823256 KB ok
75 Correct 1688 ms 823292 KB ok
76 Correct 2001 ms 839420 KB ok
77 Correct 1999 ms 839508 KB ok
78 Partially correct 2336 ms 861604 KB partial
79 Correct 1708 ms 838484 KB ok
80 Partially correct 1549 ms 833668 KB partial
81 Partially correct 1522 ms 831176 KB partial
82 Partially correct 1590 ms 834896 KB partial
83 Partially correct 2697 ms 884216 KB partial
84 Partially correct 1276 ms 823364 KB partial
85 Partially correct 1288 ms 823276 KB partial
86 Partially correct 1323 ms 823168 KB partial
87 Partially correct 1335 ms 823400 KB partial
88 Correct 1375 ms 823376 KB ok
89 Partially correct 1479 ms 823284 KB partial
90 Partially correct 1440 ms 823108 KB partial
91 Partially correct 1477 ms 823208 KB partial
92 Correct 1794 ms 861012 KB ok
93 Correct 1855 ms 872512 KB ok
94 Correct 1530 ms 838652 KB ok
95 Correct 1444 ms 831316 KB ok
96 Correct 1449 ms 828756 KB ok
97 Correct 1428 ms 826964 KB ok
98 Correct 1360 ms 824816 KB ok
99 Correct 2191 ms 868180 KB ok
100 Partially correct 1590 ms 823868 KB partial
101 Partially correct 1836 ms 823896 KB partial
102 Partially correct 1603 ms 823968 KB partial
103 Partially correct 1592 ms 823500 KB partial
104 Partially correct 1642 ms 823376 KB partial
105 Partially correct 1648 ms 823452 KB partial
106 Partially correct 1707 ms 823532 KB partial
107 Correct 1633 ms 823744 KB ok
108 Correct 1789 ms 831588 KB ok
109 Correct 1735 ms 828784 KB ok