QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#263145 | #7743. Grand Finale | ucup-team1447 | WA | 110ms | 107464kb | C++14 | 2.3kb | 2023-11-24 15:56:44 | 2023-11-24 15:56:46 |
Judging History
answer
// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
int T, n, m, p[5005][5005], dp[5005][5005], c1[5005], c2[5005];
std::string s, t;
bool check(int size)
{
for (int i = 0; i <= c1[n]; ++i)
if (p[i][size - m] && dp[p[i][size - m]][i] <= c2[p[i][size - m]] - (size - m))
return true;
return false;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin >> T;
while (T--)
{
std::cin >> m >> n >> t >> s;
s = t + s;
n = n + m;
for (int i = 0; i != n; ++i)
{
c1[i + 1] = c1[i] + (s[i] == 'Q');
c2[i + 1] = c2[i] + (s[i] == 'B');
}
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
p[i][j] = 0;
p[0][0] = m;
for (int i = 0; i <= c1[n]; ++i)
for (int j = 0; j <= c2[n]; ++j)
{
if (i < c1[p[i][j]])
p[i + 1][j] = std::min(n, p[i][j] + 1);
if (j < c2[p[i][j]])
p[i][j + 1] = std::min(n, p[i][j] + 2);
}
for (int i = 0; i <= n; ++i)
dp[n][i] = 0;
for (int i = n; i--;)
for (int j = 0; j <= n; ++j)
{
dp[i][j] = INT_MAX / 2;
if (j)
dp[i][j] = std::min(dp[i][j], dp[i + 1][j - 1 + (s[i] == 'Q')] - (s[i] == 'B'));
dp[i][j] =
std::min(dp[i][j],
std::max(1,
dp[std::min(n, i + 2)][j + (s[i] == 'Q')] - (s[i] == 'B') + 1));
}
// for (int i = 0; i <= c1[n]; ++i)
// for (int j = 0; j <= c2[n]; ++j)
// std::cout << p[i][j] << " \n"[j == c2[n]];
// std::cout << c1[n] << ' ' << c2[n] << std::endl;
if (p[c1[n]][c2[n]] == 0)
{
std::cout << "IMPOSSIBLE" << std::endl;
continue;
}
// std::cout << check(3) << std::endl;
int l = m, r = n;
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
std::cout << l << std::endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5912kb
input:
2 2 6 BG BQWBWW 4 6 GQBW WWWWQB
output:
3 IMPOSSIBLE
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 110ms
memory: 107464kb
input:
13 184 887 WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...
output:
1071 1881 2601 712 1006 2557 IMPOSSIBLE 2310 1506 1766 33 160 2452
result:
wrong answer 1st lines differ - expected: '184', found: '1071'