QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402752 | #7990. 广播 | zzzwsnd | WA | 1ms | 3584kb | C++14 | 834b | 2024-05-01 12:54:38 | 2024-05-01 12:54:39 |
Judging History
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'