QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #733144 | #9536. Athlete Welcome Ceremony | 0123456789_1# | WA | 13ms | 90652kb | C++14 | 2.7kb | 2024-11-10 17:25:22 | 2024-11-10 17:25:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main(){
long n,q,i,j,k,i1,q1,q2,q3;
static long dp[310][160][160][3],s[160][160][160];
char z[310];
scanf("%ld %ld\n%s\n",&n,&q,z+1);
z[0]=z[n+1]='d';
i1=0;
for(i=1;i<=n;i++){
if(z[i]!='?')continue;
i1++;
if(i1==1){
if(z[i-1]!='a'&&z[i+1]!='a')dp[1][1][0][0]=1;
if(z[i-1]!='b'&&z[i+1]!='b')dp[1][0][1][1]=1;
if(z[i-1]!='c'&&z[i+1]!='c')dp[1][0][0][2]=1;
continue;
}
for(j=0;j<=min(i1,n+1>>1);j++){
for(k=0;k<=min(i1-j,n+1>>1);k++){
if(i1-j-k>n+1>>1)continue;
if(z[i-1]=='?'){
if(z[i+1]!='a'){
dp[i1][j][k][0]=dp[i1-1][j-1][k][1]+dp[i1-1][j-1][k][2];
}
if(z[i+1]!='b'){
dp[i1][j][k][1]=dp[i1-1][j][k-1][0]+dp[i1-1][j][k-1][2];
}
if(z[i+1]!='c'){
dp[i1][j][k][2]=dp[i1-1][j][k][0]+dp[i1-1][j][k][1];
}
}else{//if(i1==2&&j==1&&k==0)printf("a");
if(z[i-1]!='a'&&z[i+1]!='a'){//if(i1==2&&j==1&&k==0)printf("a");
dp[i1][j][k][0]=dp[i1-1][j-1][k][0]+dp[i1-1][j-1][k][1]+dp[i1-1][j-1][k][2];
}
if(z[i-1]!='b'&&z[i+1]!='b'){
dp[i1][j][k][1]=dp[i1-1][j][k-1][0]+dp[i1-1][j][k-1][1]+dp[i1-1][j][k-1][2];
}
if(z[i-1]!='c'&&z[i+1]!='c'){
dp[i1][j][k][2]=dp[i1-1][j][k][0]+dp[i1-1][j][k][1]+dp[i1-1][j][k][2];
}
}
}
}
}//printf("%ld - \n",dp[1][0][0][2]);
for(i=0;i<=min(i1,n+1>>1);i++){
for(j=0;j<=min(i1-i,n+1>>1);j++){
if(i1-i-j>n+1>>1)continue;
s[i+1][j+1][i1-i-j+1]=dp[i1][i][j][0]+dp[i1][i][j][1]+dp[i1][i][j][2];
//printf("%ld %ld %ld %ld\n",i,j,i1-i-j,s[i+1][j+1][i1-i-j+1]);
}
}
for(i=1;i<=151;i++){
for(j=1;j<=151;j++){
for(k=1;k<=151;k++){//if(i==0&&j==0&&k==4)printf("*%ld ",s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]);
s[i][j][k]+=s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]-s[i-1][j-1][k]-s[i-1][j][k-1]-s[i][j-1][k-1]+s[i-1][j-1][k-1];
}
}
}//printf(" s222=%ld \n",s[2][2][2]);
while(q--){
scanf("%ld %ld %ld\n",&q1,&q2,&q3);
q1=min(q1,(long)150);
q2=min(q2,(long)150);
q3=min(q3,(long)150);//printf("%ld %ld %ld\n",q1,q2,q3);
printf("%ld\n",s[q1+1][q2+1][q3+1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 37128kb
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: 8ms
memory: 39128kb
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: 10ms
memory: 35136kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 13ms
memory: 34812kb
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: 3ms
memory: 37004kb
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: 0
Accepted
time: 4ms
memory: 36992kb
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:
8 8 8 0 8 8 6 8 8 8 8 0 0 0 1 8 4 8 8 8 2 4 1 8 1 6 0 2 8 6 8 8 1 4 2 8 8 0 0 8 2 0 8 8 8 4 8 8 8 8 2 0 0 4 8 8 1 8 7 6 7 0 8 8 8 0 4 7 8 4 0 8 0 4 8 8 8 7 8 4 7 2 8 8 8 0 2 2 8 8 8 4 4 0 8 0 8 8 1 1
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 7ms
memory: 53636kb
input:
50 100 b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a??? 35 43 36 12 49 47 7 11 34 38 44 22 42 17 10 49 8 38 18 26 44 6 18 14 28 29 6 48 32 47 29 15 48 1 5 33 24 17 18 10 27 32 19 10 34 2 23 9 14 24 39 46 12 34 9 49 26 21 8 46 43 43 3 31 16 2 8 27 7 24 41 35 17 25 31 0 13 47 24 31 23 33 40 30 36 39...
output:
34272000 31599360 497244 34272000 17637520 12290752 34272000 93044 415832 34272000 34272000 0 34272000 16360704 27933952 0 34272000 33886976 7896832 12290752 718 24 0 34272000 34272000 0 34272000 34272000 34272000 32254720 0 5666944 34256640 34272000 34272000 12290752 30493248 34256640 20630016 0 10...
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 36936kb
input:
100 1000 c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca 13 11 4 4 17 20 14 5 2 16 14 15 8 12 17 19 5 11 5 17 12 20 7 6 19 10 1 6 5 0 13 1 9 7 17 1 20 4 16 11 12 18 19 2 16 18 1 11 19 16 3 7 1 0 6 9 16 6 9 16 6 20 7 0 16 20 1 2 8 16 5 20 18 14 18 ...
output:
16 15 14 16 16 16 16 16 8 2 16 8 16 16 16 16 16 2 16 16 16 0 1 16 16 5 1 5 16 16 16 16 16 15 16 13 16 15 2 16 16 1 8 16 16 16 15 0 16 15 16 16 16 16 8 8 16 16 16 16 16 16 8 16 16 1 8 8 16 16 1 16 1 0 16 2 2 16 7 16 16 8 16 16 16 16 1 16 14 16 16 16 16 5 16 16 14 16 11 16 15 11 2 1 8 16 16 7 16 5 16 ...
result:
ok 1000 lines
Test #9:
score: -100
Wrong Answer
time: 3ms
memory: 90652kb
input:
100 1000 ?????c??????????????????????????b???a????a?????????????????????????c???????????????????????????????? 43 38 20 27 40 32 39 27 33 28 50 43 50 3 46 38 46 14 42 48 10 45 25 28 49 10 49 38 17 42 41 49 22 41 18 44 46 47 25 17 44 35 34 43 22 47 42 32 32 44 40 36 41 24 45 38 45 49 44 18 42 34 32 43...
output:
2302847131085177796 1231030111893990552 -7121649646039721732 6060064949104886864 10104 634744475662311848 188759480606016 3818135784889638920 285391905843968 -3445154106014984128 2223433454215415604 -4084974334209149078 7284229812967896384 3740860968457109280 -2149490141467713024 568799557075147584 ...
result:
wrong answer 1st lines differ - expected: '490475656', found: '2302847131085177796'