QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402752#7990. 广播zzzwsndWA 1ms3584kbC++14834b2024-05-01 12:54:382024-05-01 12:54:39

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 12:54:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3584kb
  • [2024-05-01 12:54:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int M =2200;
int a[M],b[M];
int dp[M][M];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[n-i+1]; 
	}
	for(int i=1;i<=m;i++){
		cin>>b[m-i+1];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i]==b[j]||a[i]==1||b[j]==1){
				dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
				
			}
			else
			dp[i][j]=max(dp[i-1][j-1],max(dp[i][j-1],dp[i-1][j]));
			//cout<<dp[i][j]<<' ';
		}
		//cout<<endl;
	}
	int flag=0;
	int sum=0;
	if(n>=m){
		for(int i=m;i<=n;i++){
			if(dp[i][m]+i-m==i){
				flag=1;
				sum=i-m;
				break;	
			}
		}
	}
	else{
		for(int i=n;i<=m;i++){
			if(dp[n][i]+i-n==i){
				flag=1;
				sum=i-n;
				break;	
			}
		}		
	}
	if(!flag){
		sum=(n+m-2*dp[n][m]);
	}
	//cout<<flag<<endl;
	cout<<sum;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

4 2
2 1 3 2
4 2

output:

1

result:

ok single line: '1'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3500kb

input:

1 1
2
3

output:

2

result:

wrong answer 1st lines differ - expected: '1', found: '2'