QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #716970 | #9536. Athlete Welcome Ceremony | lzr010506# | WA | 2ms | 10504kb | C++14 | 2.1kb | 2024-11-06 16:32:25 | 2024-11-06 16:32:25 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
#define MAXN 312
using namespace std;
int n,m;
char s[MAXN];
int dp[MAXN][MAXN][MAXN][3];
int sum[MAXN][MAXN][MAXN];
int sum_e[MAXN];
void ADD(int &x,int y){
x=(x+y)%MOD;
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
int cnt[3]={0};
for(int i=1;i<=n;i++){
if(s[i]!='?')cnt[s[i]-'a']++;
}
dp[0][0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
for(int t=0;t<3;t++){
int e = i+j+k+t;
//printf("dp[%d][%d][%d][%d]=%d %c %d\n",i,j,k,t,dp[i][j][k][t],s[i+1],e);
if((s[i+1] == 'a' || s[i+1]=='?') && (t!=0 || e==0)){
ADD(dp[i+1][j+1][k][0],dp[i][j][k][t]);
}
if((s[i+1] == 'b' || s[i+1]=='?') && (t!=1 || e==0) ){
ADD(dp[i+1][j][k+1][1],dp[i][j][k][t]);
}
if((s[i+1]=='c' || s[i+1]=='?') && (t!=2 || e==0)){
ADD(dp[i+1][j][k][2],dp[i][j][k][t]);
}//printf("%d\n",dp[i+1][j+1][k][0]);
}
}
}
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++){
int k = n-i-j;
if(k>=0){
sum[i+1][j+1][k+1]= (dp[n][i][j][0]+0ll+dp[n][i][j][1]+dp[n][i][j][2])%MOD;
}
}
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n+1;j++)
for(int k=1;k<=n+1;k++){
sum[i][j][k] = (0ll+sum[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1]+MOD+MOD+MOD)%MOD;
}
//printf("%d\n",dp[2][1][0][2]);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x+=cnt[0];y+=cnt[1];z+=cnt[2];
x=min(x,n+1);y=min(y,n+1);z=min(z,n+1);
printf("%d\n",sum[x+1][y+1][z+1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8016kb
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: 1ms
memory: 8208kb
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: 1ms
memory: 5936kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 10504kb
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: 2ms
memory: 10468kb
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:
0 0 11 16 11 16 0 0 0 0
result:
wrong answer 1st lines differ - expected: '16', found: '0'