QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #243170 | #7743. Grand Finale | qkm66666 | WA | 92ms | 29112kb | C++17 | 2.8kb | 2023-11-07 21:44:31 | 2023-11-07 21:44:31 |
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'&&j>=1){
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>=1){
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],max(dp[i][j],1));
}
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;;){
if(dp[i][cnt[0]]<=cnt[1]){
Ans=cur;
break;
}
if(i>=m||(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
2
4 8
BBBB
WWWWWWWG
4 8
BBBB
WWWWWWGW
*/
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: 3852kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 92ms
memory: 28600kb
input:
13 184 887 WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...
output:
184 372 316 161 118 534 IMPOSSIBLE 631 183 276 33 160 643
result:
ok 13 lines
Test #4:
score: 0
Accepted
time: 45ms
memory: 29112kb
input:
32 887 278 BQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQQWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQBWW...
output:
887 981 15 18 60 9 108 268 475 17 52 12 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE 76 14 182 907 537 19 19 233 10 38 111 143 103 159 14 IMPOSSIBLE 225
result:
ok 32 lines
Test #5:
score: 0
Accepted
time: 16ms
memory: 16880kb
input:
120 37 178 BQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBG BWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQQWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQ 21 184 QQBQBWQQQBWQWQBWWBQQG QWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBB...
output:
37 24 41 23 46 22 21 24 31 178 23 26 50 IMPOSSIBLE 23 24 25 24 IMPOSSIBLE 43 17 37 35 46 44 42 25 44 33 33 8 14 21 IMPOSSIBLE 36 32 50 79 IMPOSSIBLE 42 34 42 12 IMPOSSIBLE 32 35 44 13 50 IMPOSSIBLE 47 IMPOSSIBLE 37 16 42 38 IMPOSSIBLE 34 37 30 45 IMPOSSIBLE 46 42 42 34 30 32 27 IMPOSSIBLE 25 14 39 3...
result:
ok 120 lines
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3996kb
input:
543 4 37 WBQG BBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWW 2 20 QG BQQQWQBBQQWQQBBWWQWQ 6 47 WBQWWG WWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQB 20 41 WWBWQWQWBWBQWWQBQQQG BWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBB 12 38 BQQWBQBQBWBG QQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQ 3 15 BWG WBQQQWQWBQBBQBW 2 12 WG...
output:
9 4 IMPOSSIBLE 20 12 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE 8 IMPOSSIBLE 6 IMPOSSIBLE 18 IMPOSSIBLE 18 10 19 19 14 6 IMPOSSIBLE IMPOSSIBLE 7 8 12 IMPOSSIBLE 6 15 13 15 14 13 IMPOSSIBLE 20 5 18 9 11 13 12 10 8 IMPOSSIBLE 9 6 12 14 8 8 IMPOSSIBLE IMPOSSIBLE 19 16 9 15 12 20 10 IMPOSSIBLE 5 12 IMPOSSIBLE 16 ...
result:
wrong answer 43rd lines differ - expected: '14', found: 'IMPOSSIBLE'