比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
美丽的感觉 |
最终得分 |
100 |
用户昵称 |
Mealy |
运行时间 |
0.016 s |
代码语言 |
C++ |
内存使用 |
96.04 MiB |
提交时间 |
2017-05-23 20:04:25 |
显示代码纯文本
//2598
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
const int nmax = 10010;
using namespace std;
int N;
char Sa[nmax] = {0};
char Sb[nmax] = {0};
int Ba[nmax] = {0};
int Bb[nmax] = {0};
int Ra[nmax] = {0};
int Rb[nmax] = {0};
bool F[nmax][nmax] = {0};
void PreDo(){
scanf("%d",&N);
scanf("%s%s",Sa + 1,Sb + 1);
Ba[0] = 0;
Ra[0] = 0;
for(int i = 1;i <= N;i++){
Ra[i] = Ra[i-1];
Ba[i] = Ba[i-1];
Sa[i] == '0' ? Ra[i]++ : Ba[i]++;
}
Bb[0] = 0;
Rb[0] = 0;
for(int i = 1;i <= N;i++){
Rb[i] = Rb[i-1];
Bb[i] = Bb[i-1];
Sb[i] == '0' ? Rb[i]++ : Bb[i]++;
}
}
bool Check(int x, int y){
if(x==0&&y==0){
return 0;
}
else{
if(F[x-1][y]||F[x][y-1]){
return 1;
}
}
return 0;
}
void DP(){
/*
for(int i=1;i<=N;i++){
printf("%d %d\n",Rb[i],Bb[i]);
}
*/
F[0][0] = 1;
for(int i = 0;i <= N;i++){
for(int j = 0;j <= N;j++){
if(Check(i, j)){
if(abs(Ra[i] + Rb[j] - Ba[i] - Bb[j]) <= 1){
F[i][j] = 1;
}
}
}
}
/*
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
printf("%d ",F[i][j]);
}
printf("\n");
}
*/
F[N][N]==1 ? printf("Accepted!\n") : printf("Impossible!\n");
}
int main(){
freopen("card_.in","r",stdin);
freopen("card_.out","w",stdout);
PreDo();
DP();
return 0;
}