oj.uz

Submission #840586

# Submission time Handle Problem Language Result Execution time Memory
840586 2023-08-31T14:10:27 Z blackyuki Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1082 ms 691148 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define fi first
#define se second
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    ll n=N+2;
    vvi v(n,vi(n,1));
    rep(i,N)rep(j,N)v[i+1][j+1]=F[i][j];
    vvvi next(2,vvi(n,vi(n,n))),prev(2,vvi(n,vi(n,-1)));
    rep(i,n)rep(j,n){
        prev[v[i][j]][i][j]=j;
        if(j>0)prev[1-v[i][j]][i][j]=prev[1-v[i][j]][i][j-1];
    }
    rep(i,n)for(int j=n-1;j>=0;j--){
        next[v[i][j]][i][j]=j;
        if(j<n-1)next[1-v[i][j]][i][j]=next[1-v[i][j]][i][j+1];
    }
    vvi up(n,vi(n)),down(n,vi(n)),upl(n,vi(n,-1)),upr(n,vi(n,-1)),downl(n,vi(n,n)),downr(n,vi(n,n));
    rep(i,n)rep(j,n){
        if(v[i][j])up[i][j]=i+1;
        else up[i][j]=up[i-1][j];
    }
    for(int i=n-1;i>=0;i--)rep(j,n){
        if(v[i][j])down[i][j]=i-1;
        else down[i][j]=down[i+1][j];
    }
    rep(i,n)rep(j,n)if(!v[i][j]){
        chmax(upl[i][j],up[i][j]);
        upl[i][j+1]=upl[i][j];
        chmin(downl[i][j],down[i][j]);
        downl[i][j+1]=downl[i][j];
    }
    rep(i,n)for(ll j=n-1;j>=0;j--)if(!v[i][j]){
        chmax(upr[i][j],up[i][j]);
        upr[i][j-1]=upr[i][j];
        chmin(downr[i][j],down[i][j]);
        downr[i][j-1]=downr[i][j];
    }
    vector<vector<map<P,ll>>> dp(n,vector<map<P,ll>>(n));
    rep(i,n)REP(j,1,n-1)if(v[i][j-1]&&!v[i][j]){
        ll l=j,r=next[1][i][j]-1;
        ll u=upr[i][j],d=downr[i][j];
        if(u==i)dp[l][r][P(u,d)]=(r-l+1)*(d-u+1);
    }
    auto f1=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=upr[u-1][l],nd=d;
        if(next[1][d+1][l]>r+1)return;
        if(next[1][d+1][l]==r+1)nd=downr[d+1][l];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    auto f2=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=upl[u-1][r],nd=d;
        if(prev[1][d+1][r]<l-1)return;
        if(prev[1][d+1][r]==l-1)nd=downl[d+1][r];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    auto f3=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=u,nd=downr[d+1][l];
        if(next[1][u-1][l]>r+1)return;
        if(next[1][u-1][l]==r+1)nd=upr[u-1][l];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    auto f4=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=u,nd=downl[d+1][r];
        if(prev[1][u-1][r]<l-1)return;
        if(prev[1][u-1][r]==l-1)nd=upl[u-1][r];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    ll ans=0;
    rep(l,n)for(ll r=n-1;r>=l;r--){
        for(auto x:dp[l][r]){
            chmax(ans,x.se);
            ll u=x.fi.fi,d=x.fi.se;
            ll cur=l;
            if(!v[u-1][l]){
                f1(u,d,l,next[1][u-1][l]-1,x.se);
                cur=next[1][u-1][l];
            }
            while(true){
                cur=next[0][u-1][cur];
                if(cur>r)break;
                ll t=next[1][u-1][cur];
                if(t>r){
                    f2(u,d,cur,r,x.se);
                    break;
                }
                f1(u,d,cur,next[1][u-1][cur]-1,x.se);
                cur=next[1][u-1][cur];
            }
            cur=l;
            if(!v[d+1][l]){
                f3(u,d,l,next[1][d+1][l]-1,x.se);
                cur=next[1][d+1][l];
            }
            while(true){
                cur=next[0][d+1][cur];
                if(cur>r)break;
                ll t=next[1][d+1][cur];
                if(t>r){
                    f4(u,d,cur,r,x.se);
                    break;
                }
                f3(u,d,cur,next[1][d+1][cur]-1,x.se);
                cur=next[1][d+1][cur];
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 2 ms 1748 KB ok
8 Correct 32 ms 36032 KB ok
9 Correct 555 ms 566140 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 1 ms 336 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 1 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 1 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 1 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 1 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 0 ms 212 KB ok

Subtask #4
18.0 / 18.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 336 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 1 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 1 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 1 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 1 ms 212 KB ok
26 Correct 0 ms 212 KB ok
27 Correct 0 ms 212 KB ok
28 Correct 0 ms 212 KB ok
29 Correct 0 ms 212 KB ok
30 Correct 1 ms 340 KB ok
31 Correct 1 ms 468 KB ok
32 Correct 1 ms 468 KB ok
33 Correct 0 ms 340 KB ok
34 Correct 0 ms 340 KB ok
35 Correct 1 ms 340 KB ok
36 Correct 1 ms 340 KB ok
37 Correct 0 ms 340 KB ok
38 Correct 1 ms 340 KB ok
39 Correct 0 ms 340 KB ok
40 Correct 0 ms 340 KB ok
41 Correct 1 ms 468 KB ok
42 Correct 66 ms 40640 KB ok
43 Correct 70 ms 41628 KB ok
44 Correct 41 ms 37128 KB ok
45 Correct 39 ms 36652 KB ok
46 Correct 54 ms 39048 KB ok
47 Correct 35 ms 36052 KB ok
48 Correct 35 ms 36052 KB ok
49 Correct 37 ms 36044 KB ok
50 Correct 53 ms 43788 KB ok
51 Correct 40 ms 37076 KB ok
52 Correct 34 ms 36168 KB ok
53 Correct 41 ms 36044 KB ok
54 Correct 36 ms 36044 KB ok
55 Correct 42 ms 36172 KB ok
56 Correct 34 ms 36036 KB ok
57 Correct 40 ms 39884 KB ok
58 Correct 41 ms 40524 KB ok
59 Correct 43 ms 41036 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 2 ms 1748 KB ok
9 Correct 32 ms 36032 KB ok
10 Correct 555 ms 566140 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 1 ms 336 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Correct 1 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 1 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 1 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 0 ms 212 KB ok
27 Correct 0 ms 212 KB ok
28 Correct 1 ms 212 KB ok
29 Correct 0 ms 212 KB ok
30 Correct 1 ms 212 KB ok
31 Correct 0 ms 212 KB ok
32 Correct 0 ms 212 KB ok
33 Correct 0 ms 212 KB ok
34 Correct 0 ms 212 KB ok
35 Correct 1 ms 340 KB ok
36 Correct 1 ms 468 KB ok
37 Correct 1 ms 468 KB ok
38 Correct 0 ms 340 KB ok
39 Correct 0 ms 340 KB ok
40 Correct 1 ms 340 KB ok
41 Correct 1 ms 340 KB ok
42 Correct 0 ms 340 KB ok
43 Correct 1 ms 340 KB ok
44 Correct 0 ms 340 KB ok
45 Correct 0 ms 340 KB ok
46 Correct 1 ms 468 KB ok
47 Correct 66 ms 40640 KB ok
48 Correct 70 ms 41628 KB ok
49 Correct 41 ms 37128 KB ok
50 Correct 39 ms 36652 KB ok
51 Correct 54 ms 39048 KB ok
52 Correct 35 ms 36052 KB ok
53 Correct 35 ms 36052 KB ok
54 Correct 37 ms 36044 KB ok
55 Correct 53 ms 43788 KB ok
56 Correct 40 ms 37076 KB ok
57 Correct 34 ms 36168 KB ok
58 Correct 41 ms 36044 KB ok
59 Correct 36 ms 36044 KB ok
60 Correct 42 ms 36172 KB ok
61 Correct 34 ms 36036 KB ok
62 Correct 40 ms 39884 KB ok
63 Correct 41 ms 40524 KB ok
64 Correct 43 ms 41036 KB ok
65 Correct 1082 ms 640116 KB ok
66 Correct 1020 ms 615188 KB ok
67 Correct 673 ms 586956 KB ok
68 Correct 545 ms 568780 KB ok
69 Correct 656 ms 584212 KB ok
70 Correct 756 ms 598320 KB ok
71 Correct 527 ms 567584 KB ok
72 Correct 522 ms 566096 KB ok
73 Correct 515 ms 566032 KB ok
74 Correct 514 ms 566080 KB ok
75 Correct 515 ms 566148 KB ok
76 Correct 940 ms 691148 KB ok
77 Correct 942 ms 691124 KB ok
78 Correct 573 ms 576056 KB ok
79 Correct 613 ms 571048 KB ok
80 Correct 595 ms 569524 KB ok
81 Correct 631 ms 569576 KB ok
82 Correct 694 ms 573588 KB ok
83 Correct 796 ms 588188 KB ok
84 Correct 522 ms 566188 KB ok
85 Correct 499 ms 566116 KB ok
86 Correct 532 ms 566164 KB ok
87 Correct 544 ms 567016 KB ok
88 Correct 572 ms 566128 KB ok
89 Correct 557 ms 566060 KB ok
90 Correct 549 ms 566036 KB ok
91 Correct 553 ms 566032 KB ok
92 Correct 634 ms 578068 KB ok
93 Correct 665 ms 580668 KB ok
94 Correct 581 ms 570512 KB ok
95 Correct 554 ms 568396 KB ok
96 Correct 534 ms 567564 KB ok
97 Correct 522 ms 567104 KB ok
98 Correct 509 ms 566544 KB ok
99 Correct 760 ms 631672 KB ok
100 Correct 654 ms 628940 KB ok
101 Correct 635 ms 622804 KB ok
102 Correct 678 ms 628900 KB ok
103 Correct 690 ms 639548 KB ok
104 Correct 699 ms 643344 KB ok
105 Correct 714 ms 646412 KB ok
106 Correct 707 ms 649540 KB ok
107 Correct 682 ms 648856 KB ok
108 Correct 540 ms 571596 KB ok
109 Correct 545 ms 571724 KB ok