Submission #344486


Source Code Expand

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <queue>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
 
#define MOD 1000000007
 
int dp[255][10][255][255];
 
int main(){
  int N, X;
  string str;
  cin >> N >> X;
  cin >> str;
 
  if(str[0] == '?'){
    rep(i,10){
      if(i==2){
        dp[0][i][1][0] = 1;
      }else{
        dp[0][i][0][0] = 1;
      }
    }
  }else{
    int t = str[0]-'0';
    if(t==2){
      dp[0][t][1][0] = 1;
    }else{
      dp[0][t][0][0] = 1;
    }
  }
 
  rep(i,N-1){
    rep(j,10){
      rep(k,N+1){
        rep(l,X+1){
          //cout << i << " " << j << " " << k << " " << l << " " << dp[i][j][k][l] << endl;
          
          if(str[i+1]=='?'){
            rep(t,10){
              if(t==2){
                if(j==5){
                  dp[i+1][t][k+1][l] += dp[i][j][k][l];
                  dp[i+1][t][k+1][l] %= MOD;
                }else{
                  dp[i+1][t][1][l] += dp[i][j][k][l];
                  dp[i+1][t][1][l] %= MOD;
                }
              }
              else if(t==5){
                if(j==2){
                  dp[i+1][t][k+1][min(X,l+(k+1)/2)] += dp[i][j][k][l];
                  dp[i+1][t][k+1][min(X,l+(k+1)/2)] %= MOD;
                }else{
                  dp[i+1][t][0][l] += dp[i][j][k][l];
                  dp[i+1][t][0][l] %= MOD;
                }              
              }
              else{
                dp[i+1][t][0][l] += dp[i][j][k][l];
                dp[i+1][t][0][l] %= MOD;
              }
            }
          }else{
            int t = str[i+1]-'0';
            if(t==2){
              if(j==5){
                dp[i+1][t][k+1][l] += dp[i][j][k][l];
                dp[i+1][t][k+1][l] %= MOD;
              }else{
                dp[i+1][t][1][l] += dp[i][j][k][l];
                dp[i+1][t][1][l] %= MOD;
              }
            }
            else if(t==5){
              if(j==2){
                dp[i+1][t][k+1][min(X,l+(k+1)/2)] += dp[i][j][k][l];
                dp[i+1][t][k+1][min(X,l+(k+1)/2)] %= MOD;
              }else{
                dp[i+1][t][0][l] += dp[i][j][k][l];
                dp[i+1][t][0][l] %= MOD;
              }              
            }
            else{
              dp[i+1][t][0][l] += dp[i][j][k][l];
              dp[i+1][t][0][l] %= MOD;
            }
          }
        }
      }
    }
  }
 
  ll ret = 0;
  ll all = 1;
  rep(i,N){
    if(str[i] == '?'){
      all = (all * 10LL)%MOD;
    }
  }
  rep(i,10){
    rep(j,N){
      rep(k,X){
        ret = (ret + dp[N-1][i][j][k])%MOD;
      }
    }
  }
  cout << (all - ret + MOD)%MOD << endl;
  return 0;
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User phyllo
Language C++ (G++ 4.6.4)
Score 0
Code Size 3125 Byte
Status WA
Exec Time 2061 ms
Memory 137972 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 2
AC × 13
WA × 1
TLE × 8
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 88 ms 2740 KB
sample_02.txt AC 44 ms 3640 KB
subtask1_01.txt AC 38 ms 2740 KB
subtask1_02.txt AC 36 ms 2744 KB
subtask1_03.txt WA 37 ms 2736 KB
subtask1_04.txt AC 38 ms 2712 KB
subtask1_05.txt AC 453 ms 31504 KB
subtask1_06.txt AC 659 ms 30260 KB
subtask1_07.txt AC 399 ms 27156 KB
subtask1_08.txt AC 689 ms 13844 KB
subtask1_09.txt AC 276 ms 12220 KB
subtask1_10.txt AC 101 ms 6156 KB
subtask1_11.txt AC 914 ms 63280 KB
subtask1_12.txt TLE 2049 ms 25592 KB
subtask1_13.txt AC 977 ms 96404 KB
subtask1_14.txt TLE 2050 ms 38360 KB
subtask1_15.txt TLE 2050 ms 38420 KB
subtask1_16.txt TLE 2053 ms 39320 KB
subtask1_17.txt TLE 2047 ms 27516 KB
subtask1_18.txt TLE 2061 ms 55064 KB
subtask1_19.txt TLE 2046 ms 27540 KB
subtask1_20.txt TLE 2051 ms 38708 KB
subtask1_21.txt AC 910 ms 137972 KB
subtask1_22.txt AC 738 ms 83024 KB