UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212754#3828. Bxpjqz03ms5124kbC++1.7kb2024-10-20 10:32:192024-10-20 14:37:09

answer

#include <bits/stdc++.h>
using namespace std;
int n,m,t;
int a[10005][10005],sz[1000005],js=0,maxn=0,ans[1000005];
int fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//下 右 上 左
void dfs(int x,int y){
	sz[js++]=a[x][y];
	if((x<0||x>=n||y<0||y>=m)||(a[x+1][y]<a[x][y]&&a[x-1][y]<a[x][y]&&a[x][y+1]<a[x][y]&&a[x][y-1]<a[x][y])){
		if(js>maxn){
			maxn=js;
			for(int i = 0;i < maxn;i++){
				ans[i]=sz[i];
			}
		}
		if(js==maxn){
			int ct1=0,ct2=0;
			for(int i = 0;i < maxn;i++){
				ct1+=ans[i];
				ct2+=sz[i];
			}
			if(ct2<ct1){
				for(int i = 0;i < maxn;i++){
					ans[i]=sz[i];
				}
			}
		}
		return;
	}
	for(int i = 0;i < 4;i++){
		int dx=x+fx[i][0];
		int dy=y+fx[i][1];
		if(dx>=0&&dx<n&&dy>=0&&dy<m){
			if(a[dx][dy]>a[x][y]){
				dfs(dx,dy);
				sz[--js]=0;
			}
		}
	}
}
int main(){
	cin >> t;
	for(int q=0;q<t;q++){
		cin >> n >> m;
		int zans[1000005]={0},zmaxn=0;
		js=0,maxn=0;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				cin >> a[i][j];
			}
		}
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				js=0,maxn=0;
				dfs(i,j);
				if(maxn>zmaxn){
					for(int w=0;w<maxn;w++){
						zans[w]=ans[w];
					}
					zmaxn=maxn;
				}
				if(maxn==zmaxn){
					int ct1=0,ct2=0;
					for(int w = 0;w < zmaxn;w++){
						ct1+=zans[i];
						ct2+=ans[i];
					}
					if(ct2<ct1){
						for(int i = 0;i < zmaxn;i++){
							zans[i]=ans[i];
						}
					}
				}
				maxn=0;
				js=0;
			}
		}
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				a[i][j]=0;
			}
		}
		cout << zmaxn << endl;
		for(int i = 0;i < zmaxn;i++){
			cout << zans[i] << " ";
		}
		cout << endl;
	}
	
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 5124kb

input:

10
3 3
0 1 2
3 4 5
6 7 8
3 3
0 1 2
3 4 5
6 8 7
3 3
0 1 2
3 4 5
7 6 8
3 3
0 1 2
3 4 5
7 8 6
3 3
0 1 2...

output:

5
0 1 2 5 8 
6
0 1 2 5 7 8 
5
0 1 2 5 8 
6
0 1 2 5 6 8 
5
0 1 2 5 7 
7
0 1 2 5 6 7 8 
5
0 1 2 6 8 
6...

result:

wrong answer 57th numbers differ - expected: '2', found: '4'

Subtask #2:

score: 0
Time Limit Exceeded

Test #3:

score: 0
Time Limit Exceeded

input:

10
22 45
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

10
2 100000
143604 106821 145034 44402 118718 156663 77133 28800 81890 12336 191537 118894 103331 75...

output:

11
1106 7782 40570 46626 46722 59706 75312 81513 143585 154546 199163 
9
9688 35806 66263 69546 9469...

result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

10
1 200000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #7:

score: 0
Time Limit Exceeded

input:

10
145 1379
140324 86968 96426 123781 39754 103720 60835 118904 114639 53717 27146 110309 39232 5608...

output:

14
8850 11113 25989 34151 36456 84869 93686 115053 144522 160408 175609 177211 186680 198340 
14
701...

result: