Submission #228676
Source Code Expand
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n; ++i)
using namespace std;
long long mod=1000000007;
long long dp[22][60][60];
char str[60][22];
long long solve(int a,int b,int c){
if(~dp[a][b][c])return dp[a][b][c];
if(b+1==c&&!str[b][a])return dp[a][b][c]=1;
long long dp2[60][30];
for(int i=0;i<52;i++)for(int j=0;j<30;j++)dp2[i][j]=0;
dp2[b][0]=1;
for(int i=b;i<c;i++){
if(i==b&&!str[i][a]){
dp2[i+1][0]=dp2[i][0];
continue;
}
for(int j=0;j<26;j++){
if(!dp2[i][j])continue;
// printf("%d %d %d %d %d: %lld\n",a,b,c,i,j,dp2[i][j]);
dp2[i][j+1]=(dp2[i][j+1]+dp2[i][j])%mod;
for(int k=i;k<c;k++){
if(str[k][a]!='?'&&str[k][a]!='a'+j)break;
dp2[k+1][j+1]=(dp2[k+1][j+1]+dp2[i][j]*solve(a+1,i,k+1))%mod;
}
}
}
long long ret=0;
for(int i=0;i<27;i++)ret=(ret+dp2[c][i]);
// printf("%d %d %d: %lld\n",a,b,c,ret);
return dp[a][b][c]=ret%mod;
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%s",str[i]);
for(int i=0;i<22;i++)for(int j=0;j<60;j++)for(int k=0;k<60;k++)dp[i][j][k]=-1;
printf("%lld\n",solve(0,0,n));
}
Submission Info
Submission Time
2014-09-13 11:08:53+0900
Task
B - Dictionary
User
semi_exp_
Language
C++11 (GCC 4.8.1)
Score
0
Code Size
1185 Byte
Status
TLE
Exec Time
4031 ms
Memory
1828 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:38:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:39:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<n;i++)scanf("%s",str[i]);
^
Judge Result
Set Name
All
Score / Max Score
0 / 100
Status
Set Name
Test Cases
All
000, 001, 002, 003, 004, 005, 006, 007, 008, 009, 010, 011, 012, 013, 900, 901
Case Name
Status
Exec Time
Memory
000
AC
24 ms
1444 KB
001
AC
24 ms
1436 KB
002
TLE
4031 ms
1828 KB
003
AC
26 ms
1700 KB
004
AC
24 ms
1572 KB
005
AC
24 ms
1572 KB
006
AC
23 ms
1568 KB
007
AC
23 ms
1696 KB
008
AC
25 ms
1568 KB
009
AC
26 ms
1696 KB
010
AC
25 ms
1568 KB
011
AC
26 ms
1564 KB
012
AC
26 ms
1572 KB
013
AC
25 ms
1700 KB
900
AC
24 ms
1448 KB
901
AC
23 ms
1564 KB