QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #712709 | #9536. Athlete Welcome Ceremony | ucup-team1769 | WA | 151ms | 228880kb | C++14 | 3.6kb | 2024-11-05 16:44:01 | 2024-11-05 16:44:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300 + 10;
const int mod = 1e9 + 7;
int dp[N][3][N][N];
int res[N][N][N];
void solve()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
s = ' ' + s;
int sum = 0, cnt = 0;
for (int i = 1; i <= n; i++)
{
if (s[i] == '?')
sum++;
}
if (s[1] == '?')
{
dp[1][0][1][0] = dp[1][1][0][1] = dp[1][2][0][0] = 1;
}
else
{
int k = s[1] - 'a';
dp[1][k][0][0] = 1;
}
for (int i = 2; i <= n; i++)
{
if (s[i] == '?')
{
for (int k = 0; k < 3; k++)
{
if (s[i - 1] - 'a' == k)
continue;
if (i < n && s[i + 1] - 'a' == k)
continue;
for (int a = 0; a <= sum; a++)
{
for (int b = 0; b <= sum; b++)
{
if (k == 0)
dp[i][0][a + 1][b] = (dp[i][0][a + 1][b] + dp[i - 1][1][a][b] + dp[i - 1][2][a][b]) % mod;
else if (k == 1)
dp[i][1][a][b + 1] = (dp[i][1][a][b + 1] + dp[i - 1][0][a][b] + dp[i - 1][2][a][b]) % mod;
else
dp[i][2][a][b] = (dp[i][2][a][b] + dp[i - 1][0][a][b] + dp[i - 1][1][a][b]) % mod;
}
}
}
}
else
{
int k = s[i] - 'a';
for (int a = 0; a <= sum; a++)
{
for (int b = 0; b <= sum; b++)
{
dp[i][k][a][b] = max({dp[i][k][a][b], dp[i - 1][0][a][b], dp[i - 1][1][a][b], dp[i - 1][2][a][b]});
}
}
}
}
// for (int i = 1; i <= n; i++)
// {
// for (int k = 0; k < 3; k++)
// {
// for (int a = 0; a <= sum; a++)
// {
// for (int b = 0; b <= sum; b++)
// {
// cout << i << ' ' << k << ' ' << a << ' ' << b << ' ' << dp[i][k][a][b] << endl;
// }
// }
// }
// }
for (int a = 0; a <= sum; a++)
{
for (int b = 0; b <= sum; b++)
{
int c = sum - a - b;
res[a + 1][b + 1][c + 1] = (dp[n][0][a][b] + dp[n][1][a][b] + dp[n][2][a][b]) % mod;
}
}
for (int a = 0; a <= 300; a++)
{
for (int b = 0; b <= 300; b++)
{
for (int c = 0; c <= 300; c++)
{
res[a + 1][b + 1][c + 1] += res[a][b + 1][c + 1] + res[a + 1][b][c + 1] + res[a + 1][b + 1][c] + res[a][b][c];
res[a + 1][b + 1][c + 1] -= res[a][b][c + 1] + res[a][b + 1][c] + res[a + 1][b][c];
res[a + 1][b + 1][c + 1] = (res[a + 1][b + 1][c + 1] + mod) % mod;
}
}
}
// for (int a = 0; a <= sum; a++)
// {
// for (int b = 0; b <= sum; b++)
// {
// for (int c = 0; c <= sum; c++)
// {
// cout << a << ' ' << b << ' ' << c << ' ' << res[a + 1][b + 1][c + 1] << endl;
// }
// }
// }
int a, b, c;
while (q--)
{
cin >> a >> b >> c;
cout << res[a + 1][b + 1][c + 1] << '\n';
}
}
signed main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 151ms
memory: 226336kb
input:
6 3 a?b??c 2 2 2 1 1 1 1 0 2
output:
3 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 135ms
memory: 228880kb
input:
6 3 ?????? 2 2 2 2 3 3 3 3 3
output:
30 72 96
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 138ms
memory: 226220kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 141ms
memory: 226904kb
input:
10 10 acab?cbaca 0 2 0 1 1 2 4 2 3 1 1 1 3 5 1 0 5 2 2 2 0 1 2 5 4 3 0 1 1 3
output:
0 1 1 1 1 0 1 1 1 1
result:
ok 10 lines
Test #5:
score: -100
Wrong Answer
time: 131ms
memory: 228520kb
input:
10 10 ?c?c?cbac? 10 5 1 5 8 7 9 2 6 5 7 1 5 2 6 5 6 5 5 10 3 9 1 10 2 5 9 1 2 9
output:
14 14 10 14 10 14 14 6 10 2
result:
wrong answer 1st lines differ - expected: '16', found: '14'