oj.uz

Submission #844931

# Submission time Handle Problem Language Result Execution time Memory
844931 2023-09-06T09:19:38 Z Lib Soccer Stadium (IOI23_soccer) C++17
8 / 100
 4500 ms 7260 KB 
#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&&k+b<p2&&k-(a-b-1)>p1){
						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

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 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2392 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 813 ms 4740 KB ok
8 Execution timed out 4543 ms 7260 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2392 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 2396 KB ok
11 Correct 0 ms 2396 KB ok
12 Correct 0 ms 2392 KB ok
13 Correct 1 ms 2392 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 1 ms 2392 KB ok
16 Correct 0 ms 2396 KB ok
17 Correct 1 ms 2392 KB ok
18 Correct 1 ms 2392 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 0 ms 2396 KB ok
21 Correct 1 ms 2392 KB ok
22 Incorrect 1 ms 2396 KB wrong
23 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 813 ms 4740 KB ok
9 Execution timed out 4543 ms 7260 KB Time limit exceeded
10 Halted 0 ms 0 KB -