Submission #343357


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,i+2){
        rep(l,X+2){
          //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][1][l] += dp[i][j][k][l];
                  dp[i+1][t][1][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][1][l] += dp[i][j][k][l];
                dp[i+1][t][1][l] %= MOD;
              }              
            }
            else{
              dp[i+1][t][0][l] += dp[i][j][k][l];
              dp[i+1][t][0][l] %= MOD;
            }
          }
        }
      }
    }
  }

  int ret = 0;
  rep(i,10){
    rep(j,N){
      ret = (ret + dp[N-1][i][j][X])%MOD;
    }
  }
  cout << ret << endl;
  return 0;
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 2
AC × 8
WA × 8
TLE × 6
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 34 ms 1100 KB
sample_02.txt AC 32 ms 1712 KB
subtask1_01.txt AC 29 ms 1164 KB
subtask1_02.txt WA 30 ms 1100 KB
subtask1_03.txt AC 33 ms 992 KB
subtask1_04.txt WA 32 ms 980 KB
subtask1_05.txt AC 219 ms 16988 KB
subtask1_06.txt AC 295 ms 15496 KB
subtask1_07.txt WA 195 ms 14288 KB
subtask1_08.txt WA 340 ms 8112 KB
subtask1_09.txt AC 143 ms 6928 KB
subtask1_10.txt WA 60 ms 3272 KB
subtask1_11.txt AC 448 ms 33740 KB
subtask1_12.txt TLE 2049 ms 28264 KB
subtask1_13.txt AC 492 ms 50700 KB
subtask1_14.txt TLE 2050 ms 40528 KB
subtask1_15.txt WA 1926 ms 42720 KB
subtask1_16.txt TLE 2039 ms 43784 KB
subtask1_17.txt TLE 2047 ms 33004 KB
subtask1_18.txt AC 1039 ms 33744 KB
subtask1_19.txt TLE 2045 ms 33256 KB
subtask1_20.txt TLE 2050 ms 42000 KB
subtask1_21.txt WA 459 ms 74044 KB
subtask1_22.txt WA 354 ms 43532 KB