QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #717464 | #9536. Athlete Welcome Ceremony | Swd146296# | WA | 1ms | 9980kb | C++17 | 2.8kb | 2024-11-06 18:01:48 | 2024-11-06 18:01:52 |
Judging History
answer
#include<string>
#include<iostream>
typedef long long ll;
ll mod = 1000000007;
int m, n, q;
std::string s;
int pos[307];
int dp[3][307][307][307];
int res[307][307];//res[i][j] represents i*a, j*b and (n-i-j)*c
int sum[307][307];//sum[i] is the prefix sum of res[i]
int getsum(int i, int l, int r)
{
if(r < l)
return 0;
if(l == 0)
return sum[i][r];
return ((sum[i][r] - sum[i][l - 1]) % mod + mod) % mod;
}
int main()
{
std::cin >> m >> q >> s;
s = " " + s + " ";
for(int i = 1; i <= m; i++)
{
if(s[i] == '?')
{
++n;
pos[n] = i;
}
}
if(s[pos[1] - 1] != 'a' && s[pos[1] + 1] != 'a')
dp[0][1][0][0] = 1;
if(s[pos[1] - 1] != 'b' && s[pos[1] + 1] != 'b')
dp[1][0][1][0] = 1;
if(s[pos[1] - 1] != 'c' && s[pos[1] + 1] != 'c')
dp[2][0][0][1] = 1;
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n - i; j++)
{
for(int k = 0; k <= n - i - j; k++)
{
if(i + j + k == 1)
continue;
int now = pos[i + j + k];
if(i)
{
if(s[now - 1] == 'a' || s[now + 1] == 'a')
continue;
if(s[now - 1] == '?')
dp[0][i][j][k] = (dp[0][i][j][k] + dp[1][i-1][j][k] + dp[2][i-1][j][k])% mod;
else
dp[0][i][j][k] = (dp[0][i][j][k] + dp[0][i-1][j][k] + dp[1][i-1][j][k] + dp[2][i-1][j][k])% mod;
}
if(j)
{
if(s[now - 1] == 'b' || s[now + 1] == 'b')
continue;
if(s[now - 1] == '?')
dp[1][i][j][k] = (dp[1][i][j][k] + dp[0][i][j-1][k] + dp[2][i][j-1][k])% mod;
else
dp[1][i][j][k] = (dp[1][i][j][k] + dp[0][i][j-1][k] + dp[1][i][j-1][k] + dp[2][i][j-1][k])% mod;
}
if(k)
{
if(s[now - 1] == 'c' || s[now + 1] == 'c')
continue;
if(s[now - 1] == '?')
dp[2][i][j][k] = (dp[2][i][j][k] + dp[0][i][j][k-1] + dp[1][i][j][k-1])% mod;
else
dp[2][i][j][k] = (dp[2][i][j][k] + dp[0][i][j][k-1] + dp[1][i][j][k-1] + dp[2][i][j][k-1])% mod;
}
}
}
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n - i; j++)
{
int k = n - i - j;
res[i][j] = (dp[0][i][j][k] + dp[1][i][j][k] + dp[2][i][j][k]) % mod;
if(j)
sum[i][j] = (sum[i][j - 1] + res[i][j]) % mod;
else
sum[i][j] = res[i][0];
}
}
while(q--)
{
long long output = 0;
int a, b, c;
std::cin >> a >> b >> c;
a = std::min(n, a);
b = std::min(n, b);
c = std::min(n, c);
for(int i = 0; i <= a; i++)
{
int res = n - i; // number of (b + c)
int l = res - c; // i*a l*b c*c
if(l < 0)
l = 0;
int r = res; // i*a (n-i)*b 0*c
if(r > b)
r = b;
// for(int fuck = 0; fuck <= n; fuck++)
// {
// if(l <= fuck && fuck <= r)
// putchar('*');
// else putchar(' ');
// }
output = (output + getsum(i, l, r)) % mod;
}
std::cout << output << std::endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5704kb
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: 0ms
memory: 8048kb
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: 0ms
memory: 9980kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5656kb
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: 0
Accepted
time: 1ms
memory: 7712kb
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:
16 16 11 16 11 16 16 5 11 0
result:
ok 10 lines
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 7736kb
input:
50 100 ?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca 8 3 8 2 4 8 8 7 3 0 9 2 10 8 7 7 6 5 4 10 2 6 9 3 3 6 6 9 10 8 2 5 8 8 1 0 3 5 0 1 0 6 5 0 8 6 5 5 1 7 9 7 7 10 4 7 5 6 6 4 10 1 2 4 1 7 10 0 8 7 6 3 1 9 1 4 7 2 8 4 0 8 6 1 5 10 4 5 8 2 5 8 4 4 5 9 5 2 1 1 10 9 4 10 1 8 4 3 8 9 9 8 0 1 0 8 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '8', found: '0'