oj.uz

Submission #1096952

# Submission time Handle Problem Language Result Execution time Memory
1096952 2024-10-05T14:32:58 Z azberjibiou Soccer Stadium (IOI23_soccer) C++17
100 / 100
 881 ms 94556 KB 
#include "soccer.h"
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
 
typedef long long ll;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
const int mxN=2055;
const int mxM=35000;
const int mxK=1000000000;
const int MOD=998244353;
const ll INF=1e17;
struct uf{
    int par[mxN], l[mxN], r[mxN];
    void init(int n){for(int i=0;i<=n;i++) par[i]=i, l[i]=r[i]=i;}
    int fp(int a){return par[a]==a ? a : par[a]=fp(par[a]);}
    void mrg(int a, int b){ // a -> b merge
        int p=fp(a), q=fp(b);
        l[q]=min(l[q], l[p]);
        r[q]=max(r[q], r[p]);
        par[p]=q;
    } 
};
int N;
int A[mxN][mxN], S[mxN][mxN];
int H[mxN];
int dp[mxN][mxN];
vector <pair<pii, int>> prop;
vector <pii> trash;
int ans;
void input(){
    cin >> N;
    for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) A[i][j]=1;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cin >> A[i][j];
}
void init(int n, vector <vector<int>> F){
    N=n;
    for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) A[i][j]=1;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) A[i][j]=F[i-1][j-1];
}
void make_prefix_sum(){
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j]=S[i][j-1]+A[i][j];
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j]+=S[i-1][j];
}
int sum(int x1, int x2, int y1, int y2){return S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];}
vector <int> ct[mxN];
uf U1;
pii expand(int yl, int yr, int xr, int h){
    int nyl=yl, nyr=yr;
    int s=nyr, e=N;
    while(s!=e){
        int mid=(s+e)/2;
        if(sum(xr-h+1, xr, yr+1, mid)==0) s=mid+1;
        else e=mid;
    }
    nyr=(sum(xr-h+1, xr, yr+1, s)==0 ? s : s-1);
    s=1, e=yl;
    while(s!=e){
        int mid=(s+e)/2;
        if(sum(xr-h+1, xr, mid, nyl-1)==0) e=mid;
        else s=mid+1;
    }
    nyl=s;
    return pii(nyl, nyr);
}
void sweep(){
    for(int i=N;i>=1;i--){
        //set H
        for(int j=1;j<=N;j++) H[j]--;
        for(int j=1;j<=N;j++){
            if(H[j]==-1){
                H[j]=0;
                while(A[i-H[j]][j]==0) H[j]++; // using x, y coordinate as math
            }
        }
        H[0]=H[N+1]=0;
        //sweep
        for(int j=0;j<=N;j++) ct[j].clear();
        for(int j=1;j<=N;j++) ct[H[j]].push_back(j);
        //for(int j=1;j<=N;j++) printf("H[%d]=%d\n", j, H[j]);
        U1.init(N);
        //propagation
        for(auto [lr, val] : prop){
            auto [l, r]=lr;
            dp[l][r]=max(dp[l][r], val);
        }
        prop.clear();
        for(int j=N;j>=1;j--){
            //printf("j=%d\n", j);
            for(int x : ct[j]){
                if(H[x]<=H[x-1]) U1.mrg(x-1, x);
                if(H[x]<=H[x+1]) U1.mrg(x+1, x);
            }
            for(int x : ct[j]) if(U1.fp(x)==x){
                int yl=U1.l[x], yr=U1.r[x], xr=i;
                //set dp to rectangle area
                dp[yl][yr]=max(dp[yl][yr], j*(yr-yl+1));
                trash.emplace_back(yl, yr);
                ans=max(ans, dp[yl][yr]);
                //printf("dp[%d][%d][%d]=%d\n", xr, yl, yr, dp[xr][pii(yl, yr)]);
                //(yl, yr, xr) -> (yl, yr, xr-1)
                if(j!=1){
                    auto [nyl, nyr]=expand(yl, yr, xr-1, j-1);
                    prop.emplace_back(pii(nyl, nyr), dp[yl][yr]+(yl-nyl+nyr-yr)*(j-1));
                    //printf("nyl, nyr, xr-1 = %d %d %d\n", nyl, nyr, xr-1);
                }
                // (yl, yr, xr) -> (yl-1, yr, xr) or (yl, yr+1, xr)
                int nh=max(H[yl-1], H[yr+1]);
                if(nh!=0){
                    auto [nyl, nyr]=expand(yl, yr, xr, nh);
                    dp[nyl][nyr]=max(dp[nyl][nyr], dp[yl][yr]+(yl-nyl+nyr-yr)*nh);
                    //printf("nyl, nyr, xr, nh = %d %d %d %d\n", nyl, nyr, xr, nh);
                }
            }
        }
        for(auto [l, r] : trash) dp[l][r]=0;
        trash.clear();
    }
}
int biggest_stadium(int n, std::vector<std::vector<int>> F)
{
    init(n, F);
    make_prefix_sum();
    sweep();
    return ans;
}
/*
int main()
{
    gibon
    input();
    make_prefix_sum();
    sweep();
    cout << ans;
}
*/

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 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 496 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 2 ms 1576 KB ok
8 Correct 20 ms 10232 KB ok
9 Correct 297 ms 88028 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 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 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 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 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 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 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 1 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 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

Subtask #4
18.0 / 18.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 496 KB ok
5 Correct 1 ms 604 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 0 ms 348 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 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 348 KB ok
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 604 KB ok
29 Correct 1 ms 604 KB ok
30 Correct 1 ms 860 KB ok
31 Correct 1 ms 860 KB ok
32 Correct 0 ms 860 KB ok
33 Correct 1 ms 860 KB ok
34 Correct 1 ms 752 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 0 ms 604 KB ok
40 Correct 0 ms 604 KB ok
41 Correct 1 ms 860 KB ok

Subtask #5
16.0 / 16.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 496 KB ok
5 Correct 1 ms 604 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 0 ms 348 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 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 348 KB ok
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 604 KB ok
29 Correct 1 ms 604 KB ok
30 Correct 1 ms 860 KB ok
31 Correct 1 ms 860 KB ok
32 Correct 0 ms 860 KB ok
33 Correct 1 ms 860 KB ok
34 Correct 1 ms 752 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 0 ms 604 KB ok
40 Correct 0 ms 604 KB ok
41 Correct 1 ms 860 KB ok
42 Correct 42 ms 11256 KB ok
43 Correct 44 ms 11232 KB ok
44 Correct 43 ms 11752 KB ok
45 Correct 44 ms 11908 KB ok
46 Correct 56 ms 11464 KB ok
47 Correct 21 ms 10228 KB ok
48 Correct 25 ms 9976 KB ok
49 Correct 22 ms 9964 KB ok
50 Correct 30 ms 10736 KB ok
51 Correct 30 ms 11408 KB ok
52 Correct 20 ms 9716 KB ok
53 Correct 19 ms 9464 KB ok
54 Correct 20 ms 9460 KB ok
55 Correct 20 ms 10072 KB ok
56 Correct 18 ms 9752 KB ok
57 Correct 28 ms 12080 KB ok
58 Correct 29 ms 12016 KB ok
59 Correct 32 ms 11864 KB ok

Subtask #6
30.0 / 30.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 496 KB ok
5 Correct 1 ms 604 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 2 ms 1576 KB ok
9 Correct 20 ms 10232 KB ok
10 Correct 297 ms 88028 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 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 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 604 KB ok
24 Correct 1 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 1 ms 860 KB ok
36 Correct 1 ms 860 KB ok
37 Correct 0 ms 860 KB ok
38 Correct 1 ms 860 KB ok
39 Correct 1 ms 752 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 1 ms 604 KB ok
43 Correct 1 ms 604 KB ok
44 Correct 0 ms 604 KB ok
45 Correct 0 ms 604 KB ok
46 Correct 1 ms 860 KB ok
47 Correct 42 ms 11256 KB ok
48 Correct 44 ms 11232 KB ok
49 Correct 43 ms 11752 KB ok
50 Correct 44 ms 11908 KB ok
51 Correct 56 ms 11464 KB ok
52 Correct 21 ms 10228 KB ok
53 Correct 25 ms 9976 KB ok
54 Correct 22 ms 9964 KB ok
55 Correct 30 ms 10736 KB ok
56 Correct 30 ms 11408 KB ok
57 Correct 20 ms 9716 KB ok
58 Correct 19 ms 9464 KB ok
59 Correct 20 ms 9460 KB ok
60 Correct 20 ms 10072 KB ok
61 Correct 18 ms 9752 KB ok
62 Correct 28 ms 12080 KB ok
63 Correct 29 ms 12016 KB ok
64 Correct 32 ms 11864 KB ok
65 Correct 713 ms 80344 KB ok
66 Correct 369 ms 80000 KB ok
67 Correct 295 ms 79996 KB ok
68 Correct 813 ms 92508 KB ok
69 Correct 881 ms 83544 KB ok
70 Correct 851 ms 82004 KB ok
71 Correct 693 ms 93788 KB ok
72 Correct 337 ms 88288 KB ok
73 Correct 355 ms 74964 KB ok
74 Correct 371 ms 75616 KB ok
75 Correct 343 ms 75360 KB ok
76 Correct 387 ms 84064 KB ok
77 Correct 442 ms 84160 KB ok
78 Correct 492 ms 85852 KB ok
79 Correct 313 ms 80004 KB ok
80 Correct 287 ms 80220 KB ok
81 Correct 312 ms 80224 KB ok
82 Correct 356 ms 80340 KB ok
83 Correct 360 ms 80180 KB ok
84 Correct 281 ms 73556 KB ok
85 Correct 283 ms 73304 KB ok
86 Correct 319 ms 74076 KB ok
87 Correct 285 ms 75088 KB ok
88 Correct 288 ms 80608 KB ok
89 Correct 302 ms 88160 KB ok
90 Correct 321 ms 88416 KB ok
91 Correct 323 ms 81380 KB ok
92 Correct 302 ms 80000 KB ok
93 Correct 303 ms 79996 KB ok
94 Correct 295 ms 80108 KB ok
95 Correct 290 ms 80476 KB ok
96 Correct 269 ms 80484 KB ok
97 Correct 265 ms 80332 KB ok
98 Correct 266 ms 80224 KB ok
99 Correct 563 ms 80736 KB ok
100 Correct 466 ms 94556 KB ok
101 Correct 470 ms 94364 KB ok
102 Correct 493 ms 94416 KB ok
103 Correct 508 ms 93904 KB ok
104 Correct 520 ms 93492 KB ok
105 Correct 516 ms 93396 KB ok
106 Correct 510 ms 92860 KB ok
107 Correct 499 ms 92516 KB ok
108 Correct 358 ms 80732 KB ok
109 Correct 400 ms 81760 KB ok