oj.uz

Submission #840212

# Submission time Handle Problem Language Result Execution time Memory
840212 2023-08-31T08:22:40 Z Fysty Soccer Stadium (IOI23_soccer) C++17
64 / 100
 316 ms 500392 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];
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) return dp[pos][l][r];
    pii tmp=extend(pos,l,r);
    if(tmp.F<pos)
    {
        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;
    }
    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:55:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid=ql+qr>>1;
      |                 ~~^~~
soccer.cpp:63:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid=ql+qr+1>>1;
      |                 ~~~~~^~
soccer.cpp: In function 'int calc(int, int, int)':
soccer.cpp:91:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |             int mid=ql+qr+1>>1;
      |                     ~~~~~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 2 ms 1376 KB ok
8 Correct 20 ms 8208 KB ok
9 Runtime error 316 ms 68896 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 0 ms 340 KB ok
8 Correct 1 ms 340 KB ok
9 Correct 0 ms 340 KB ok
10 Correct 0 ms 340 KB ok
11 Correct 0 ms 340 KB ok
12 Correct 0 ms 340 KB ok
13 Correct 0 ms 340 KB ok
14 Correct 1 ms 340 KB ok
15 Correct 1 ms 340 KB ok
16 Correct 0 ms 340 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 0 ms 340 KB ok
19 Correct 0 ms 340 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 1 ms 340 KB ok
22 Correct 0 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Correct 0 ms 340 KB ok
25 Correct 0 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 0 ms 340 KB ok
28 Correct 1 ms 456 KB ok
29 Correct 0 ms 340 KB ok
30 Correct 1 ms 1364 KB ok
31 Correct 1 ms 1492 KB ok
32 Correct 1 ms 1620 KB ok
33 Correct 1 ms 724 KB ok
34 Correct 1 ms 596 KB ok
35 Correct 1 ms 468 KB ok
36 Correct 0 ms 468 KB ok
37 Correct 1 ms 468 KB ok
38 Correct 1 ms 468 KB ok
39 Correct 0 ms 468 KB ok
40 Correct 0 ms 468 KB ok
41 Correct 1 ms 1108 KB ok
42 Correct 145 ms 220792 KB ok
43 Correct 177 ms 306124 KB ok
44 Correct 49 ms 50840 KB ok
45 Correct 37 ms 32676 KB ok
46 Correct 89 ms 135696 KB ok
47 Correct 20 ms 8524 KB ok
48 Correct 24 ms 8620 KB ok
49 Correct 20 ms 8480 KB ok
50 Correct 253 ms 500392 KB ok
51 Correct 60 ms 87500 KB ok
52 Correct 19 ms 8852 KB ok
53 Correct 19 ms 6424 KB ok
54 Correct 19 ms 7124 KB ok
55 Correct 19 ms 8348 KB ok
56 Correct 18 ms 6800 KB ok
57 Correct 116 ms 134440 KB ok
58 Correct 118 ms 151788 KB ok
59 Correct 131 ms 169060 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 340 KB ok
8 Correct 2 ms 1376 KB ok
9 Correct 20 ms 8208 KB ok
10 Runtime error 316 ms 68896 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -