Submission #842468

# Submission time Handle Problem Language Result Execution time Memory
842468 2023-09-02T23:24:31 Z firewater Soccer Stadium (IOI23_soccer) C++17
70 / 100
4500 ms 175000 KB
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")


#include "soccer.h"
#include<bits/stdc++.h>
#define fs first
#define sn second
#define mp make_pair
#define MX 2023
using namespace std;
int n,now,num,ans,sl,sr,l,r,lst[MX],nxt[MX],a[MX][MX],sum[MX][MX],stl[MX][20],str[MX][20],fl[MX][MX],fr[MX][MX];
pair<int,pair<int,int> >f[MX][MX],sav;
pair<int,int> d[MX][MX];
int dd[MX];
int getl(int l,int r)
{
    int k=__lg(r-l+1);
    return min(stl[l][k],stl[r-(1<<k)+1][k]);
}
int getr(int l,int r)
{
    int k=__lg(r-l+1);
    return min(str[l][k],str[r-(1<<k)+1][k]);
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            a[i][j]=F[i-1][j-1];
            sum[i][j]=sum[i][j-1]+a[i][j];
        }
    for(int i=1;i<=n;++i){
        now=1;
        for(int j=1;j<=n;++j){
            if(a[i][j])now=j+1;
            else fl[i][j]=j-now+1;
        }
        now=n;
        for(int j=n;j>0;--j){
            if(a[i][j])now=j-1;
            else fr[i][j]=now-j+1;
        }
    }
    for(int j=1;j<=n;++j){
        for(int i=1;i<=n;++i){
            stl[i][0]=fl[i][j];
            str[i][0]=fr[i][j];
        }
        for(int k=1;k<=11;++k){
            for(int i=1;i<=n;++i){
                stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
                str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
            }
        }
        for(int i=1;i<=n;++i)
            dd[i]=0;
        lst[1]=1;
        for(int i=2;i<=n;++i){
            if(fl[i][j]==fl[i-1][j]&&fr[i][j]==fr[i-1][j])lst[i]=lst[i-1];
            else lst[i]=i;
        }
        nxt[n]=n;
        for(int i=n-1;i>0;--i){
            if(fl[i][j]==fl[i+1][j]&&fr[i][j]==fr[i+1][j])nxt[i]=nxt[i+1];
            else nxt[i]=i;
        }
        for(int i=1;i<=n;++i){
            if(i>1&&fl[i-1][j]>=fl[i][j]&&fr[i-1][j]>=fr[i][j]&&(!(fl[i-1][j]==fl[i][j]&&fr[i-1][j]==fr[i][j])))continue;
            if(i<n&&fl[i+1][j]>=fl[i][j]&&fr[i+1][j]>=fr[i][j])continue;
            f[i][i]=mp(max(0,fl[i][j]+fr[i][j]-1),mp(fl[i][j],fr[i][j]));
            d[1][++dd[1]]=(mp(i,i));
        }
        for(int len=1;len<=n;++len){
            int i,k;
            for(int g=1;g<=dd[len];++g){
                i=d[len][g].fs;k=d[len][g].sn;
                sl=f[i][k].sn.fs;
                sr=f[i][k].sn.sn;
                // if(j==5)
                // printf("%d %d %d %d              (%d %d)\n",j,i,k,f[i][k].fs,sl,sr);
                if(sl+sr<1)continue;
                ans=max(ans,f[i][k].fs);
                
                if(i>1){
                    sl=min(f[i][k].sn.fs,fl[i-1][j]);
                    sr=min(f[i][k].sn.sn,fr[i-1][j]);
                    if(sl+sr>0){
                        l=1;r=lst[i-1];
                        while(l<r){
                            int mid=l+r>>1;
                            if(getl(mid,i-1)>=sl&&getr(mid,i-1)>=sr)r=mid;
                            else l=mid+1;
                        }
                        // printf("%d %d %d:%d ----->>>> %d %d:%d          (%d %d)\n",j,i,k,f[i][k].fs,l,k,f[i][k].fs+max(sr+sl-1,0)*(i-l),sl,sr);
                        sav=mp(f[i][k].fs+max(sr+sl-1,0)*(i-l),mp(sl,sr));
                        if(sav.fs>0&&sav>f[l][k]){
                            if(f[l][k].fs==0)d[k-l+1][++dd[k-l+1]]=(mp(l,k));
                            f[l][k]=sav;
                        }
                    }
                }
                if(k<n){
                    sl=min(f[i][k].sn.fs,fl[k+1][j]);
                    sr=min(f[i][k].sn.sn,fr[k+1][j]);
                    // printf("%d %d\n",fl[k+1][j],fr[k+1][j]);
                    if(sl+sr>0){
                        l=nxt[k+1];r=n;
                        while(l<r){
                            // printf("%d %d\n",l,r);
                            int mid=l+r+1>>1;
                            if(getl(k+1,mid)>=sl&&getr(k+1,mid)>=sr)l=mid;
                            else r=mid-1;
                        }
                        // printf("%d %d %d:%d ----->>>> %d %d:%d          (%d %d)\n",j,i,k,f[i][k].fs,i,l,f[i][k].fs+max(sr+sl-1,0)*(l-k),sl,sr);
                        sav=mp(f[i][k].fs+max(sr+sl-1,0)*(l-k),mp(sl,sr));
                        if(sav.fs>0&&sav>f[i][l]){
                            if(f[i][l].fs==0)d[l-i+1][++dd[l-i+1]]=(mp(i,l));
                            f[i][l]=sav;
                        }
                    }
                }
                f[i][k]=mp(0,mp(0,0));
            }
            // for(int i=1;i<=n-len+1;++i){
            //     int k=i+len-1;
            //     ans=max(ans,f[i][k].fs);
            //     if(i>1){
            //         sl=min(f[i][k].sn.fs,fl[i-1][j]);
            //         sr=min(f[i][k].sn.sn,fr[i-1][j]);
            //         f[i-1][k]=max(f[i-1][k],mp(f[i][k].fs+max(sl+sr-1,0),mp(sl,sr)));
            //     }
            //     if(k<n){
            //         sl=min(f[i][k].sn.fs,fl[k+1][j]);
            //         sr=min(f[i][k].sn.sn,fr[k+1][j]);
            //         f[i][k+1]=max(f[i][k+1],mp(f[i][k].fs+max(sl+sr-1,0),mp(sl,sr)));
            //     }
            // }
        }
    }
    return ans;
}

Compilation message

soccer.cpp:1:30: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic error "-std=c++11"
      |                              ^~~~~~~~~~~~
soccer.cpp:23:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   23 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
soccer.cpp:30:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
soccer.cpp:32:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
soccer.cpp:46:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   46 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
In file included from soccer.cpp:51:
soccer.h:3:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
    3 | int biggest_stadium(int N, std::vector<std::vector<int>> F);
      |                                                           ^
soccer.h:3:59: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.h:3:59: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.h:3:59: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.h:3:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
soccer.h:3:59: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.h:3:59: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.h:3:59: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.cpp:62:21: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   62 | int getl(int l,int r)
      |                     ^
soccer.cpp:62:21: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.cpp:62:21: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.cpp:62:21: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.cpp:67:21: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   67 | int getr(int l,int r)
      |                     ^
soccer.cpp:67:21: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.cpp:67:21: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.cpp:67:21: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.cpp:72:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 | int biggest_stadium(int N, std::vector<std::vector<int>> F)
      |                                                           ^
soccer.cpp:72:59: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.cpp:72:59: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.cpp:72:59: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:100:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:100:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:101:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:101:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:139:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |                             int mid=l+r>>1;
      |                                     ~^~
soccer.cpp:159:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |                             int mid=l+r+1>>1;
      |                                     ~~~^~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 3 ms 15192 KB ok
8 Correct 28 ms 33628 KB ok
9 Correct 416 ms 104304 KB ok
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6488 KB ok
9 Correct 1 ms 6488 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6488 KB ok
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6488 KB ok
9 Correct 1 ms 6488 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6488 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6492 KB ok
19 Correct 1 ms 6488 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 1 ms 6492 KB ok
22 Correct 1 ms 6492 KB ok
23 Correct 1 ms 6492 KB ok
24 Correct 1 ms 6488 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 6488 KB ok
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6488 KB ok
9 Correct 1 ms 6488 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6488 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6488 KB ok
19 Correct 1 ms 6488 KB ok
20 Correct 1 ms 6492 KB ok
21 Correct 1 ms 6488 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 1 ms 6492 KB ok
24 Correct 1 ms 6492 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 6488 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 6488 KB ok
29 Correct 1 ms 6488 KB ok
30 Correct 2 ms 10840 KB ok
31 Correct 1 ms 10840 KB ok
32 Correct 1 ms 8792 KB ok
33 Correct 1 ms 8792 KB ok
34 Correct 1 ms 10840 KB ok
35 Correct 1 ms 10840 KB ok
36 Correct 1 ms 10840 KB ok
37 Correct 2 ms 8792 KB ok
38 Correct 2 ms 10840 KB ok
39 Correct 1 ms 10840 KB ok
40 Correct 1 ms 10844 KB ok
41 Correct 2 ms 11052 KB ok
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6488 KB ok
9 Correct 1 ms 6488 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6488 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6488 KB ok
19 Correct 1 ms 6488 KB ok
20 Correct 1 ms 6492 KB ok
21 Correct 1 ms 6488 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 1 ms 6492 KB ok
24 Correct 1 ms 6492 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 6488 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 6488 KB ok
29 Correct 1 ms 6488 KB ok
30 Correct 2 ms 10840 KB ok
31 Correct 1 ms 10840 KB ok
32 Correct 1 ms 8792 KB ok
33 Correct 1 ms 8792 KB ok
34 Correct 1 ms 10840 KB ok
35 Correct 1 ms 10840 KB ok
36 Correct 1 ms 10840 KB ok
37 Correct 2 ms 8792 KB ok
38 Correct 2 ms 10840 KB ok
39 Correct 1 ms 10840 KB ok
40 Correct 1 ms 10844 KB ok
41 Correct 2 ms 11052 KB ok
42 Correct 115 ms 40276 KB ok
43 Correct 73 ms 40020 KB ok
44 Correct 293 ms 46420 KB ok
45 Correct 311 ms 46168 KB ok
46 Correct 174 ms 42320 KB ok
47 Correct 33 ms 45904 KB ok
48 Correct 707 ms 43236 KB ok
49 Correct 834 ms 41068 KB ok
50 Correct 44 ms 46424 KB ok
51 Correct 53 ms 42132 KB ok
52 Correct 182 ms 32548 KB ok
53 Correct 45 ms 24216 KB ok
54 Correct 150 ms 38224 KB ok
55 Correct 287 ms 44624 KB ok
56 Correct 44 ms 31568 KB ok
57 Correct 953 ms 40188 KB ok
58 Correct 1039 ms 40032 KB ok
59 Correct 1014 ms 40188 KB ok
# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 3 ms 15192 KB ok
9 Correct 28 ms 33628 KB ok
10 Correct 416 ms 104304 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6488 KB ok
14 Correct 1 ms 6488 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6492 KB ok
19 Correct 1 ms 6488 KB ok
20 Correct 1 ms 6492 KB ok
21 Correct 1 ms 6488 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 1 ms 6488 KB ok
24 Correct 1 ms 6488 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 6488 KB ok
27 Correct 1 ms 6488 KB ok
28 Correct 1 ms 6492 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 6492 KB ok
31 Correct 1 ms 6488 KB ok
32 Correct 1 ms 6492 KB ok
33 Correct 1 ms 6488 KB ok
34 Correct 1 ms 6488 KB ok
35 Correct 2 ms 10840 KB ok
36 Correct 1 ms 10840 KB ok
37 Correct 1 ms 8792 KB ok
38 Correct 1 ms 8792 KB ok
39 Correct 1 ms 10840 KB ok
40 Correct 1 ms 10840 KB ok
41 Correct 1 ms 10840 KB ok
42 Correct 2 ms 8792 KB ok
43 Correct 2 ms 10840 KB ok
44 Correct 1 ms 10840 KB ok
45 Correct 1 ms 10844 KB ok
46 Correct 2 ms 11052 KB ok
47 Correct 115 ms 40276 KB ok
48 Correct 73 ms 40020 KB ok
49 Correct 293 ms 46420 KB ok
50 Correct 311 ms 46168 KB ok
51 Correct 174 ms 42320 KB ok
52 Correct 33 ms 45904 KB ok
53 Correct 707 ms 43236 KB ok
54 Correct 834 ms 41068 KB ok
55 Correct 44 ms 46424 KB ok
56 Correct 53 ms 42132 KB ok
57 Correct 182 ms 32548 KB ok
58 Correct 45 ms 24216 KB ok
59 Correct 150 ms 38224 KB ok
60 Correct 287 ms 44624 KB ok
61 Correct 44 ms 31568 KB ok
62 Correct 953 ms 40188 KB ok
63 Correct 1039 ms 40032 KB ok
64 Correct 1014 ms 40188 KB ok
65 Correct 2029 ms 145376 KB ok
66 Correct 533 ms 145232 KB ok
67 Correct 449 ms 143408 KB ok
68 Execution timed out 4547 ms 175000 KB Time limit exceeded
69 Halted 0 ms 0 KB -