oj.uz

Submission #842464

# Submission time Handle Problem Language Result Execution time Memory
842464 2023-09-02T23:08:21 Z firewater Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 144832 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,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;
vector<pair<int,int> >d[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)
            d[i].clear();
        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].push_back(mp(i,i));
        }
        for(int len=1;len<=n;++len){
            int i,k;
            for(int g=0;g<d[len].size();++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=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].push_back(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=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].push_back(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:61:21: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   61 | int getl(int l,int r)
      |                     ^
soccer.cpp:61:21: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.cpp:61:21: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.cpp:61:21: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.cpp:66:21: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   66 | int getr(int l,int r)
      |                     ^
soccer.cpp:66:21: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.cpp:66:21: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.cpp:66:21: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
soccer.cpp:71:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   71 | int biggest_stadium(int N, std::vector<std::vector<int>> F)
      |                                                           ^
soccer.cpp:71:59: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
soccer.cpp:71:59: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
soccer.cpp:71: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:99:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   99 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:99:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   99 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:100:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:100:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int g=0;g<d[len].size();++g){
      |                         ~^~~~~~~~~~~~~~
soccer.cpp:128:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |                             int mid=l+r>>1;
      |                                     ~^~
soccer.cpp:148:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |                             int mid=l+r+1>>1;
      |                                     ~~~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 3 ms 8540 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 2 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 3 ms 15196 KB ok
8 Correct 26 ms 30416 KB ok
9 Correct 389 ms 98896 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 3 ms 8540 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8792 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8536 KB ok
13 Correct 1 ms 8792 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10780 KB ok
17 Correct 1 ms 10588 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10768 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10588 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 1 ms 10588 KB ok
24 Correct 1 ms 10584 KB ok
25 Correct 1 ms 10588 KB ok
26 Correct 1 ms 10588 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 3 ms 8540 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8792 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8792 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 10588 KB ok
18 Correct 1 ms 10780 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10768 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 1 ms 10588 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 1 ms 10588 KB ok
26 Correct 1 ms 10584 KB ok
27 Correct 1 ms 10588 KB ok
28 Correct 1 ms 10588 KB ok
29 Correct 1 ms 10588 KB ok
30 Correct 2 ms 12848 KB ok
31 Correct 2 ms 12892 KB ok
32 Correct 2 ms 12892 KB ok
33 Correct 2 ms 12892 KB ok
34 Correct 2 ms 12892 KB ok
35 Correct 2 ms 12888 KB ok
36 Correct 2 ms 13048 KB ok
37 Correct 2 ms 12892 KB ok
38 Correct 2 ms 12892 KB ok
39 Correct 2 ms 12892 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 12892 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 3 ms 8540 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8792 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8792 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 10588 KB ok
18 Correct 1 ms 10780 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10768 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 1 ms 10588 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 1 ms 10588 KB ok
26 Correct 1 ms 10584 KB ok
27 Correct 1 ms 10588 KB ok
28 Correct 1 ms 10588 KB ok
29 Correct 1 ms 10588 KB ok
30 Correct 2 ms 12848 KB ok
31 Correct 2 ms 12892 KB ok
32 Correct 2 ms 12892 KB ok
33 Correct 2 ms 12892 KB ok
34 Correct 2 ms 12892 KB ok
35 Correct 2 ms 12888 KB ok
36 Correct 2 ms 13048 KB ok
37 Correct 2 ms 12892 KB ok
38 Correct 2 ms 12892 KB ok
39 Correct 2 ms 12892 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 12892 KB ok
42 Correct 109 ms 38824 KB ok
43 Correct 69 ms 38600 KB ok
44 Correct 287 ms 39156 KB ok
45 Correct 303 ms 38888 KB ok
46 Correct 163 ms 38820 KB ok
47 Correct 31 ms 38748 KB ok
48 Correct 733 ms 35844 KB ok
49 Correct 856 ms 36032 KB ok
50 Correct 37 ms 38736 KB ok
51 Correct 51 ms 38748 KB ok
52 Correct 182 ms 27372 KB ok
53 Correct 38 ms 24720 KB ok
54 Correct 147 ms 30800 KB ok
55 Correct 295 ms 33716 KB ok
56 Correct 42 ms 28556 KB ok
57 Correct 913 ms 33080 KB ok
58 Correct 965 ms 33252 KB ok
59 Correct 965 ms 33284 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 3 ms 8540 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 2 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 3 ms 15196 KB ok
9 Correct 26 ms 30416 KB ok
10 Correct 389 ms 98896 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8792 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8792 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 1 ms 10780 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 1 ms 10588 KB ok
26 Correct 1 ms 10768 KB ok
27 Correct 1 ms 10588 KB ok
28 Correct 1 ms 10588 KB ok
29 Correct 1 ms 10588 KB ok
30 Correct 1 ms 10588 KB ok
31 Correct 1 ms 10584 KB ok
32 Correct 1 ms 10588 KB ok
33 Correct 1 ms 10588 KB ok
34 Correct 1 ms 10588 KB ok
35 Correct 2 ms 12848 KB ok
36 Correct 2 ms 12892 KB ok
37 Correct 2 ms 12892 KB ok
38 Correct 2 ms 12892 KB ok
39 Correct 2 ms 12892 KB ok
40 Correct 2 ms 12888 KB ok
41 Correct 2 ms 13048 KB ok
42 Correct 2 ms 12892 KB ok
43 Correct 2 ms 12892 KB ok
44 Correct 2 ms 12892 KB ok
45 Correct 2 ms 12892 KB ok
46 Correct 2 ms 12892 KB ok
47 Correct 109 ms 38824 KB ok
48 Correct 69 ms 38600 KB ok
49 Correct 287 ms 39156 KB ok
50 Correct 303 ms 38888 KB ok
51 Correct 163 ms 38820 KB ok
52 Correct 31 ms 38748 KB ok
53 Correct 733 ms 35844 KB ok
54 Correct 856 ms 36032 KB ok
55 Correct 37 ms 38736 KB ok
56 Correct 51 ms 38748 KB ok
57 Correct 182 ms 27372 KB ok
58 Correct 38 ms 24720 KB ok
59 Correct 147 ms 30800 KB ok
60 Correct 295 ms 33716 KB ok
61 Correct 42 ms 28556 KB ok
62 Correct 913 ms 33080 KB ok
63 Correct 965 ms 33252 KB ok
64 Correct 965 ms 33284 KB ok
65 Correct 1971 ms 144172 KB ok
66 Correct 484 ms 144096 KB ok
67 Correct 423 ms 144088 KB ok
68 Execution timed out 4538 ms 144832 KB Time limit exceeded
69 Halted 0 ms 0 KB -