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
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
AC × 2
AC × 22
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