Submission #844920

#	Time	Username	Problem	Language	Result	Execution time	Memory
844920		Lib	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	4543 ms	7260 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int val[503][503];
int cntop[503];
int cnbot[503];
int mtop[503];
int mbot[503];
int dp[503][503][4];
int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
    int n=N;
	for(int i=0;i<=n+1;i++){
		for(int k=0;k<=n+1;k++){
			val[i][k]=1;
		}
	}
    for (int i = 0; i < N ; ++i)
    {
        for (int j = 0; j < N ; ++j)
        {
            val[i+1][j+1]=C[i][j];
        }
    }
 
	int p1,p2;
	int ans=0;
	int carea;
	int add;
	for(int i=1;i<=n;i++){
		for(int k=1;k<=n;k++){
			for(int l=0;i-l>=0;l++){
				if(val[i-l][k]){
					cntop[k]=l;
					break;
				}
			}
			for(int l=0;i+l<=n+1;l++){
				if(val[i+l][k]){
					cnbot[k]=l;
					break;
				}
			}	
		}
		for(int k=1;k<=n;k++){
			if(cntop[k]!=0){
			mtop[k]=cntop[k];
			mbot[k]=cnbot[k];
			p1=k-1;
			p2=k+1;
			for(int c=0;c<4;c++){
				for(int a=1;a<=n;a++){
					for(int b=1;b<=n;b++){
						dp[a][b][c]=0;
					}
				}
			dp[k][k][c]=cntop[k]+cnbot[k]-1;
			while(p1>0&&cntop[p1]){
				mtop[p1]=min(cntop[p1],mtop[p1+1]);
				mbot[p1]=min(cnbot[p1],mbot[p1+1]);
				dp[p1][k][c]=dp[p1+1][k][c]+mtop[p1]+mbot[p1]-1;
				p1--;
			}
			while(p2<=n&&cntop[p2]){
				mtop[p2]=min(cntop[p2],mtop[p2-1]);
				mbot[p2]=min(cnbot[p2],mbot[p2-1]);
				dp[k][p2][c]=dp[k][p2-1][c]+mtop[p2]+mbot[p2]-1;
				p2++;
			}
			//cout<<p1<<" "<<p2<<"\n";
				for(int a=3;a<=p2-p1-1;a++){		
					for(int b=1;b<=a-2;b++){//r:k+b, l=k-(a-b-1)
					if(c==0){
						add=mtop[k+b]-min(mtop[k+b],mtop[k-(a-b-1)]);
					}
					if(c==1){
						add=mtop[(k-(a-b-1))]-min(mtop[k+b],mtop[k-(a-b-1)]);
					}
					if(c==2){
						add=mbot[(k-(a-b-1))]-min(mbot[k+b],mbot[k-(a-b-1)]);
					}
					if(c==3){
						add=mbot[k+b]-min(mbot[k+b],mbot[k-(a-b-1)]);
					}
					if(k-(a-b-1)>0&&k+b<=n){
						if(mtop[k+b]<=mtop[k-(a-b-1)]&&mbot[k+b]<=mbot[k-(a-b-1)]||mtop[k+b]>=mtop[k-(a-b-1)]&&mbot[k+b]>=mbot[k-(a-b-1)]){
							dp[k-(a-b-1)][k+b][c]=dp[k-(a-b-1)+1][k+b-1][c]+mtop[k+b]+mbot[k+b]+mtop[k-(a-b-1)]+mbot[k-(a-b-1)]-2;
						}else{
							dp[k-(a-b-1)][k+b][c]=dp[k-(a-b-1)+1][k+b-1][c]+min(mtop[k+b],mtop[k-(a-b-1)])*2+min(mbot[k+b],mbot[k-(a-b-1)])*2-2+add;
						}
						ans=max(ans,dp[k-(a-b-1)][k+b][c]);
						//cout<<i<<" "<<k<<" "<<k-(a-b-1)<<" "<<k+b<<" "<<dp[k-(a-b-1)][k+b]<<"\n";
					}
					}
				}
				for(int a=p1+1;a<=k;a++){
					for(int b=k;b<=p2-1;b++){
						ans=max(ans,dp[a][b][c]);
					}
				}
			}
			}
		}
	}
 
    return ans;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:86:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   86 |       if(mtop[k+b]<=mtop[k-(a-b-1)]&&mbot[k+b]<=mbot[k-(a-b-1)]||mtop[k+b]>=mtop[k-(a-b-1)]&&mbot[k+b]>=mbot[k-(a-b-1)]){
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:28:6: warning: unused variable 'carea' [-Wunused-variable]
   28 |  int carea;
      |      ^~~~~
soccer.cpp:89:123: warning: 'add' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |        dp[k-(a-b-1)][k+b][c]=dp[k-(a-b-1)+1][k+b-1][c]+min(mtop[k+b],mtop[k-(a-b-1)])*2+min(mbot[k+b],mbot[k-(a-b-1)])*2-2+add;
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30