Submission #337954
Source Code Expand
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
char s[333];
const char* p="25";
int dp[333][333][333];
int n,x;
int calc(int c)
{
if( c%2 == 1 ) c -= 1;
c /= 2;
return c*(c+1)/2;
}
int solve(int a,int b,int c)
{
if( b > x ) b = x;
//printf("%d %d %d\n",a,b,c);
if( a == n ) {
b += calc(c);
return b >= x ? 1 : 0;
}
if( dp[a][b][c] >= 0 ) return dp[a][b][c];
int res = 0;
if( s[a] == '?' ) {
for( int i = 0; i <= 9; i++ ) {
if( p[c%2] == i+'0' ) {
res = (res+solve(a+1,b,c+1))%mod;
} else {
res = (res+solve(a+1,b+calc(c),i==2?1:0))%mod;
}
}
} else {
if( s[a] == p[c%2] ) {
res = (res+solve(a+1,b,c+1))%mod;
} else {
res = (res+solve(a+1,b+calc(c),s[a]=='2'?1:0))%mod;
}
}
return dp[a][b][c] = res;
}
int main(void)
{
scanf("%d%d",&n,&x);
scanf("%s",s);
memset(dp,-1,sizeof(dp));
int res = solve(0,0,0);
printf("%d\n",res);
return 0;
}
Submission Info
Submission Time
2015-02-14 17:46:40+0900
Task
A - ニコニコ文字列2
User
roxion1377
Language
C++ (G++ 4.6.4)
Score
20
Code Size
1065 Byte
Status
AC
Exec Time
1373 ms
Memory
144968 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:52:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
20 / 20
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
All
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
318 ms
144928 KB
sample_02.txt
AC
316 ms
144932 KB
subtask1_01.txt
AC
319 ms
144916 KB
subtask1_02.txt
AC
322 ms
144932 KB
subtask1_03.txt
AC
317 ms
144924 KB
subtask1_04.txt
AC
318 ms
144932 KB
subtask1_05.txt
AC
317 ms
144924 KB
subtask1_06.txt
AC
317 ms
144928 KB
subtask1_07.txt
AC
328 ms
144928 KB
subtask1_08.txt
AC
338 ms
144932 KB
subtask1_09.txt
AC
323 ms
144928 KB
subtask1_10.txt
AC
320 ms
144968 KB
subtask1_11.txt
AC
316 ms
144932 KB
subtask1_12.txt
AC
321 ms
144932 KB
subtask1_13.txt
AC
319 ms
144936 KB
subtask1_14.txt
AC
328 ms
144936 KB
subtask1_15.txt
AC
394 ms
144936 KB
subtask1_16.txt
AC
389 ms
144928 KB
subtask1_17.txt
AC
1373 ms
144940 KB
subtask1_18.txt
AC
318 ms
144924 KB
subtask1_19.txt
AC
637 ms
144936 KB
subtask1_20.txt
AC
396 ms
144928 KB
subtask1_21.txt
AC
321 ms
144932 KB
subtask1_22.txt
AC
321 ms
144860 KB