oj.uz

Submission #840320

# Submission time Handle Problem Language Result Execution time Memory
840320 2023-08-31T09:52:54 Z Fysty Soccer Stadium (IOI23_soccer) C++17
100 / 100
 3215 ms 215440 KB 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

//#include "soccer.h"

//int dp[505][505][505];
map<pair<int,pii>,int > dp;
int sum[2005][2005];
int n;

int qry(int lx,int rx,int ly,int ry){return sum[rx][ry]-sum[lx-1][ry]-sum[rx][ly-1]+sum[lx-1][ly-1];}

pii extend(int pos,int l,int r)
{
    pii ans;
    int ql=1,qr=pos;
    while(ql<qr)
    {
        int mid=ql+qr>>1;
        if(qry(mid,pos-1,l,r)>0) ql=mid+1;
        else qr=mid;
    }
    ans.F=ql;
    ql=pos,qr=n;
    while(ql<qr)
    {
        int mid=ql+qr+1>>1;
        if(qry(pos+1,mid,l,r)>0) qr=mid-1;
        else ql=mid;
    }
    ans.S=ql;
    return ans;
}

int calc(int pos,int l,int r)
{
    //cout<<pos<<" "<<l<<" "<<r<<"\n";
    //if(dp[pos][l][r]!=0)
    if(dp.find({pos,{l,r}})!=dp.end()) return dp[{pos,{l,r}}];
    pii tmp=extend(pos,l,r);
    if(tmp.F<pos)
    {
        return dp[{pos,{l,r}}]=calc(tmp.F,l,r);
        //cout<<pos<<" "<<l<<" "<<r<<": "<<dp[pos][l][r]<<"\n";
        //return dp[pos][l][r];
    }
    int mx=0;
    int cur=l;
    for(int i=l;i<=r;i++)
    {
        cur=max(cur,i);

        int ql=cur-1,qr=r;
        while(ql<qr)
        {
            int mid=ql+qr+1>>1;
            bool valid=0;
            if(pos>1&&qry(pos-1,pos-1,i,mid)==0) valid=1;
            if(tmp.S+1<=n&&qry(tmp.S+1,tmp.S+1,i,mid)==0) valid=1;
            if(valid) ql=mid;
            else qr=mid-1;
        }
        if(ql>=cur) mx=max(mx,calc(pos,i,ql)-(tmp.S-tmp.F+1)*(ql-i+1));
        cur=ql+1;
    }
    return dp[{pos,{l,r}}]=mx+(tmp.S-tmp.F+1)*(r-l+1);
    //cout<<pos<<" "<<l<<" "<<r<<": "<<dp[pos][l][r]<<"\n";
    //return dp[pos][l][r];
}

int biggest_stadium(int N,vector<vector<int> > F)
{
    n=N;
    rep1(i,n)
    {
        rep1(j,n)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+F[i-1][j-1];
        }
    }
    int ans=0;
    rep1(i,n)
    {
        ll cur=1;
        while(cur<=n)
        {
            while(cur<=n&&F[i-1][cur-1]==1) cur++;
            if(cur>n) break;
            int to=cur;
            while(to+1<=n&&F[i-1][to]==0) to++;
            ans=max(ans,calc(i,cur,to));
            cur=to+1;
        }
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'pii extend(int, int, int)':
soccer.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid=ql+qr>>1;
      |                 ~~^~~
soccer.cpp:64:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid=ql+qr+1>>1;
      |                 ~~~~~^~
soccer.cpp: In function 'int calc(int, int, int)':
soccer.cpp:93:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int mid=ql+qr+1>>1;
      |                     ~~~~~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 724 KB ok
8 Correct 18 ms 5280 KB ok
9 Correct 316 ms 47516 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 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 212 KB ok
10 Correct 1 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 1 ms 212 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 0 ms 212 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
14 Correct 1 ms 212 KB ok
15 Correct 1 ms 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 1 ms 212 KB ok
20 Correct 0 ms 340 KB ok
21 Correct 1 ms 340 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 1 ms 340 KB ok
25 Correct 0 ms 340 KB ok
26 Correct 0 ms 340 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 1 ms 340 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 1 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 1 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 212 KB ok
17 Correct 1 ms 340 KB ok
18 Correct 1 ms 340 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 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 1 ms 340 KB ok
25 Correct 1 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 0 ms 340 KB ok
28 Correct 0 ms 340 KB ok
29 Correct 1 ms 340 KB ok
30 Correct 1 ms 468 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 1 ms 340 KB ok
35 Correct 1 ms 440 KB ok
36 Correct 1 ms 340 KB ok
37 Correct 0 ms 340 KB ok
38 Correct 1 ms 436 KB ok
39 Correct 1 ms 340 KB ok
40 Correct 1 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 1 ms 344 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 1 ms 340 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 1 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 1 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 212 KB ok
17 Correct 1 ms 340 KB ok
18 Correct 1 ms 340 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 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 1 ms 340 KB ok
25 Correct 1 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 0 ms 340 KB ok
28 Correct 0 ms 340 KB ok
29 Correct 1 ms 340 KB ok
30 Correct 1 ms 468 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 1 ms 340 KB ok
35 Correct 1 ms 440 KB ok
36 Correct 1 ms 340 KB ok
37 Correct 0 ms 340 KB ok
38 Correct 1 ms 436 KB ok
39 Correct 1 ms 340 KB ok
40 Correct 1 ms 340 KB ok
41 Correct 1 ms 468 KB ok
42 Correct 89 ms 12572 KB ok
43 Correct 83 ms 14028 KB ok
44 Correct 34 ms 7524 KB ok
45 Correct 39 ms 6600 KB ok
46 Correct 70 ms 10352 KB ok
47 Correct 18 ms 5676 KB ok
48 Correct 20 ms 5480 KB ok
49 Correct 30 ms 5708 KB ok
50 Correct 57 ms 13404 KB ok
51 Correct 28 ms 7372 KB ok
52 Correct 25 ms 5716 KB ok
53 Correct 19 ms 5716 KB ok
54 Correct 26 ms 5708 KB ok
55 Correct 26 ms 5580 KB ok
56 Correct 25 ms 5716 KB ok
57 Correct 99 ms 13700 KB ok
58 Correct 94 ms 14656 KB ok
59 Correct 99 ms 15780 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 1 ms 340 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 724 KB ok
9 Correct 18 ms 5280 KB ok
10 Correct 316 ms 47516 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 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 1 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 1 ms 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 1 ms 212 KB ok
27 Correct 0 ms 340 KB ok
28 Correct 1 ms 340 KB ok
29 Correct 1 ms 340 KB ok
30 Correct 1 ms 340 KB ok
31 Correct 1 ms 340 KB ok
32 Correct 0 ms 340 KB ok
33 Correct 0 ms 340 KB ok
34 Correct 1 ms 340 KB ok
35 Correct 1 ms 468 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 1 ms 340 KB ok
40 Correct 1 ms 440 KB ok
41 Correct 1 ms 340 KB ok
42 Correct 0 ms 340 KB ok
43 Correct 1 ms 436 KB ok
44 Correct 1 ms 340 KB ok
45 Correct 1 ms 340 KB ok
46 Correct 1 ms 468 KB ok
47 Correct 89 ms 12572 KB ok
48 Correct 83 ms 14028 KB ok
49 Correct 34 ms 7524 KB ok
50 Correct 39 ms 6600 KB ok
51 Correct 70 ms 10352 KB ok
52 Correct 18 ms 5676 KB ok
53 Correct 20 ms 5480 KB ok
54 Correct 30 ms 5708 KB ok
55 Correct 57 ms 13404 KB ok
56 Correct 28 ms 7372 KB ok
57 Correct 25 ms 5716 KB ok
58 Correct 19 ms 5716 KB ok
59 Correct 26 ms 5708 KB ok
60 Correct 26 ms 5580 KB ok
61 Correct 25 ms 5716 KB ok
62 Correct 99 ms 13700 KB ok
63 Correct 94 ms 14656 KB ok
64 Correct 99 ms 15780 KB ok
65 Correct 1199 ms 160380 KB ok
66 Correct 726 ms 115840 KB ok
67 Correct 408 ms 71548 KB ok
68 Correct 375 ms 53412 KB ok
69 Correct 659 ms 78404 KB ok
70 Correct 816 ms 99848 KB ok
71 Correct 389 ms 51108 KB ok
72 Correct 292 ms 48288 KB ok
73 Correct 281 ms 48284 KB ok
74 Correct 303 ms 48328 KB ok
75 Correct 279 ms 48288 KB ok
76 Correct 1179 ms 173488 KB ok
77 Correct 1196 ms 173476 KB ok
78 Correct 395 ms 65280 KB ok
79 Correct 327 ms 56616 KB ok
80 Correct 347 ms 54684 KB ok
81 Correct 323 ms 55116 KB ok
82 Correct 380 ms 62496 KB ok
83 Correct 539 ms 84028 KB ok
84 Correct 270 ms 48460 KB ok
85 Correct 281 ms 48288 KB ok
86 Correct 282 ms 48460 KB ok
87 Correct 343 ms 50332 KB ok
88 Correct 273 ms 48348 KB ok
89 Correct 282 ms 48292 KB ok
90 Correct 271 ms 48368 KB ok
91 Correct 281 ms 48416 KB ok
92 Correct 367 ms 65084 KB ok
93 Correct 394 ms 69812 KB ok
94 Correct 308 ms 54244 KB ok
95 Correct 291 ms 51340 KB ok
96 Correct 290 ms 50468 KB ok
97 Correct 284 ms 49848 KB ok
98 Correct 283 ms 48844 KB ok
99 Correct 1177 ms 176552 KB ok
100 Correct 2757 ms 174076 KB ok
101 Correct 2713 ms 161812 KB ok
102 Correct 2977 ms 174088 KB ok
103 Correct 2990 ms 195400 KB ok
104 Correct 3215 ms 203200 KB ok
105 Correct 3193 ms 209096 KB ok
106 Correct 2940 ms 215440 KB ok
107 Correct 2701 ms 214128 KB ok
108 Correct 556 ms 86348 KB ok
109 Correct 569 ms 87140 KB ok