oj.uz

Submission #1096950

# Submission time Handle Problem Language Result Execution time Memory
1096950 2024-10-05T14:18:34 Z azberjibiou Soccer Stadium (IOI23_soccer) C++17
100 / 100
 3940 ms 306784 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];
map <pii, int> dp[mxN];
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);
        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[xr][pii(yl, yr)]=max(dp[xr][pii(yl, yr)], j*(yr-yl+1));
                ans=max(ans, dp[xr][pii(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);
                    dp[xr-1][pii(nyl, nyr)]=max(dp[xr-1][pii(nyl, nyr)], dp[xr][pii(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[xr][pii(nyl, nyr)]=max(dp[xr][pii(nyl, nyr)], dp[xr][pii(yl, yr)]+(yl-nyl+nyr-yr)*nh);
                    //printf("nyl, nyr, xr, nh = %d %d %d %d\n", nyl, nyr, xr, nh);
                }
            }
        }
    }
}
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 604 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 604 KB ok
7 Correct 2 ms 1628 KB ok
8 Correct 24 ms 10200 KB ok
9 Correct 371 ms 88164 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 1 ms 604 KB ok
6 Correct 1 ms 604 KB ok
7 Correct 0 ms 604 KB ok
8 Correct 1 ms 604 KB ok
9 Correct 0 ms 604 KB ok
10 Correct 1 ms 604 KB ok
11 Correct 1 ms 604 KB ok
12 Correct 1 ms 604 KB ok
13 Correct 1 ms 604 KB ok
14 Correct 1 ms 604 KB ok
15 Correct 1 ms 600 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 1 ms 604 KB ok
18 Correct 1 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 1 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 0 ms 604 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 604 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 1 ms 600 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 1 ms 604 KB ok
9 Correct 0 ms 604 KB ok
10 Correct 1 ms 604 KB ok
11 Correct 0 ms 604 KB ok
12 Correct 1 ms 604 KB ok
13 Correct 1 ms 604 KB ok
14 Correct 1 ms 604 KB ok
15 Correct 1 ms 604 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 1 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 1 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 1 ms 604 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 860 KB ok
31 Correct 1 ms 860 KB ok
32 Correct 1 ms 860 KB ok
33 Correct 0 ms 860 KB ok
34 Correct 1 ms 848 KB ok
35 Correct 1 ms 860 KB ok
36 Correct 1 ms 860 KB ok
37 Correct 1 ms 856 KB ok
38 Correct 1 ms 856 KB ok
39 Correct 1 ms 856 KB ok
40 Correct 1 ms 860 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 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 1 ms 600 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 1 ms 604 KB ok
9 Correct 0 ms 604 KB ok
10 Correct 1 ms 604 KB ok
11 Correct 0 ms 604 KB ok
12 Correct 1 ms 604 KB ok
13 Correct 1 ms 604 KB ok
14 Correct 1 ms 604 KB ok
15 Correct 1 ms 604 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 1 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 1 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 1 ms 604 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 860 KB ok
31 Correct 1 ms 860 KB ok
32 Correct 1 ms 860 KB ok
33 Correct 0 ms 860 KB ok
34 Correct 1 ms 848 KB ok
35 Correct 1 ms 860 KB ok
36 Correct 1 ms 860 KB ok
37 Correct 1 ms 856 KB ok
38 Correct 1 ms 856 KB ok
39 Correct 1 ms 856 KB ok
40 Correct 1 ms 860 KB ok
41 Correct 1 ms 860 KB ok
42 Correct 165 ms 21116 KB ok
43 Correct 129 ms 19320 KB ok
44 Correct 180 ms 23112 KB ok
45 Correct 161 ms 22000 KB ok
46 Correct 195 ms 22508 KB ok
47 Correct 24 ms 10744 KB ok
48 Correct 52 ms 11704 KB ok
49 Correct 51 ms 11760 KB ok
50 Correct 53 ms 17644 KB ok
51 Correct 77 ms 16608 KB ok
52 Correct 26 ms 11000 KB ok
53 Correct 21 ms 9720 KB ok
54 Correct 23 ms 10176 KB ok
55 Correct 27 ms 10988 KB ok
56 Correct 35 ms 9716 KB ok
57 Correct 86 ms 17568 KB ok
58 Correct 96 ms 18124 KB ok
59 Correct 91 ms 18920 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 0 ms 604 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 2 ms 1628 KB ok
9 Correct 24 ms 10200 KB ok
10 Correct 371 ms 88164 KB ok
11 Correct 1 ms 600 KB ok
12 Correct 1 ms 604 KB ok
13 Correct 1 ms 604 KB ok
14 Correct 0 ms 604 KB ok
15 Correct 1 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 1 ms 604 KB ok
18 Correct 1 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 1 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 1 ms 600 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 1 ms 604 KB ok
25 Correct 1 ms 604 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 1 ms 604 KB ok
28 Correct 1 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 0 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 0 ms 604 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 0 ms 604 KB ok
35 Correct 1 ms 860 KB ok
36 Correct 1 ms 860 KB ok
37 Correct 1 ms 860 KB ok
38 Correct 0 ms 860 KB ok
39 Correct 1 ms 848 KB ok
40 Correct 1 ms 860 KB ok
41 Correct 1 ms 860 KB ok
42 Correct 1 ms 856 KB ok
43 Correct 1 ms 856 KB ok
44 Correct 1 ms 856 KB ok
45 Correct 1 ms 860 KB ok
46 Correct 1 ms 860 KB ok
47 Correct 165 ms 21116 KB ok
48 Correct 129 ms 19320 KB ok
49 Correct 180 ms 23112 KB ok
50 Correct 161 ms 22000 KB ok
51 Correct 195 ms 22508 KB ok
52 Correct 24 ms 10744 KB ok
53 Correct 52 ms 11704 KB ok
54 Correct 51 ms 11760 KB ok
55 Correct 53 ms 17644 KB ok
56 Correct 77 ms 16608 KB ok
57 Correct 26 ms 11000 KB ok
58 Correct 21 ms 9720 KB ok
59 Correct 23 ms 10176 KB ok
60 Correct 27 ms 10988 KB ok
61 Correct 35 ms 9716 KB ok
62 Correct 86 ms 17568 KB ok
63 Correct 96 ms 18124 KB ok
64 Correct 91 ms 18920 KB ok
65 Correct 3022 ms 266164 KB ok
66 Correct 724 ms 133812 KB ok
67 Correct 391 ms 94904 KB ok
68 Correct 3088 ms 270020 KB ok
69 Correct 3940 ms 306784 KB ok
70 Correct 3882 ms 300780 KB ok
71 Correct 2187 ms 230748 KB ok
72 Correct 402 ms 94148 KB ok
73 Correct 698 ms 117852 KB ok
74 Correct 708 ms 117820 KB ok
75 Correct 689 ms 116832 KB ok
76 Correct 1148 ms 205488 KB ok
77 Correct 1107 ms 205408 KB ok
78 Correct 1549 ms 195716 KB ok
79 Correct 391 ms 81200 KB ok
80 Correct 381 ms 80476 KB ok
81 Correct 451 ms 88420 KB ok
82 Correct 895 ms 110892 KB ok
83 Correct 632 ms 108768 KB ok
84 Correct 334 ms 81984 KB ok
85 Correct 324 ms 77660 KB ok
86 Correct 430 ms 87648 KB ok
87 Correct 397 ms 82748 KB ok
88 Correct 292 ms 79200 KB ok
89 Correct 344 ms 89444 KB ok
90 Correct 315 ms 90568 KB ok
91 Correct 338 ms 84580 KB ok
92 Correct 406 ms 87100 KB ok
93 Correct 412 ms 91744 KB ok
94 Correct 319 ms 77276 KB ok
95 Correct 323 ms 74856 KB ok
96 Correct 326 ms 73820 KB ok
97 Correct 289 ms 73312 KB ok
98 Correct 273 ms 72640 KB ok
99 Correct 2017 ms 238112 KB ok
100 Correct 1410 ms 207988 KB ok
101 Correct 1231 ms 202504 KB ok
102 Correct 1413 ms 207936 KB ok
103 Correct 1600 ms 218176 KB ok
104 Correct 1631 ms 222556 KB ok
105 Correct 1680 ms 226240 KB ok
106 Correct 1799 ms 231772 KB ok
107 Correct 1847 ms 234984 KB ok
108 Correct 920 ms 144576 KB ok
109 Correct 1212 ms 167996 KB ok