QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #243114 | #7743. Grand Finale | qkm66666 | WA | 84ms | 29452kb | C++17 | 2.8kb | 2023-11-07 21:10:34 | 2023-11-07 21:10:34 |
Judging History
answer
#include<iostream>
using namespace std;
const int maxn=2600;
int T,n,m;
int dp[maxn][maxn];
int cur,cnt[2];
int Ans;
string H,P;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
cin>>H;
cin>>P;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
dp[i][j]=m+1;
}
}
for(int i=0;i<=m;i++){
dp[m][i]=0;
dp[m-1][i+1]=0;
}
for(int i=m;i>0;i--){
for(int j=m;j>=0;j--){
if(i>=2&&P[i-1]!='G'){
if(P[i-2]=='B'){
dp[i-2][j]=min(dp[i-2][j],dp[i][j]);
}
if(P[i-2]=='Q'){
dp[i-2][j+1]=min(dp[i-2][j+1],max(dp[i][j]-1,0));
}
dp[i-2][j+1]=min(dp[i-2][j+1],dp[i][j]);
}
if(i>=1){
if(P[i-1]=='B'&&j>0){
dp[i-1][j-1]=min(dp[i-1][j-1],dp[i][j]+1);
}
if(P[i-1]=='Q'){
dp[i-1][j]=min(dp[i-1][j],dp[i][j]);
}
dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1);
}
}
}
Ans=m+1;
cnt[0]=0;
cnt[1]=0;
cur=n;
for(int i=0;i<n;i++){
if(H[i]=='B'){
cnt[0]++;
}
if(H[i]=='Q'){
cnt[1]++;
}
}
for(int i=0;i<m;){
if(dp[i][cnt[0]]<=cnt[1]){
Ans=cur;
break;
}
if(cnt[0]==0&&cnt[1]==0){
break;
}
if(cnt[0]){
cnt[0]--;
if(P[i]=='B'){
cnt[0]++;
}
if(P[i]=='Q'){
cnt[1]++;
}
cur++;
i++;
if(i<m){
if(P[i]=='B'){
cnt[0]++;
}
if(P[i]=='Q'){
cnt[1]++;
}
i++;
}
}
else{
cnt[1]--;
if(P[i]=='B'){
cnt[0]++;
}
if(P[i]=='Q'){
cnt[1]++;
}
i++;
}
}
if(Ans==m+1){
puts("IMPOSSIBLE");
}
else{
printf("%d\n",cur);
}
}
//system("pause");
return 0;
}
/*
2
2 6
BG
BQWBWW
4 6
GQBW
WWWWQB
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
2 2 6 BG BQWBWW 4 6 GQBW WWWWQB
output:
3 IMPOSSIBLE
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 84ms
memory: 29452kb
input:
13 184 887 WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...
output:
184 372 314 161 118 534 IMPOSSIBLE 631 182 271 33 160 642
result:
wrong answer 3rd lines differ - expected: '316', found: '314'