dwangoプログラミングコンテスト

Submission #4063843

Source codeソースコード

#include <iostream>
#include <vector>
using namespace std;
const long long mod = (1e9)+7;

long long dp[253][253][130][10];

int main(){
  int N, X;
  string S;
  cin >> N >> X >> S;
  dp[0][0][0][0] += 1;
  for(int i = 0; i < N; ++i){
    for(int j = 0; j <= X; ++j){
      for(int k = 0; k < 130; ++k){
        for(int l = 0; l < 10; ++l){
          long long t = dp[i][j][k][l];
          if(t == 0) continue;
          if(S[i] == '?'){
            for(int m = 0; m < 10; ++m){
              if(l == 5 and m == 2){
                dp[i+1][j][k][m] += t;
                dp[i+1][j][k][m] %= mod;
                continue;
              }
              if(l == 2 and m == 5){
                dp[i+1][min(j+k+1,X)][k+1][m] += t;
                dp[i+1][min(j+k+1,X)][k+1][m] %= mod;
                continue;
              }
              dp[i+1][j][0][m] += t;
              dp[i+1][j][0][m] %= mod;
            }
            continue;
          }
          if(l == 2 and S[i] == '5'){
            dp[i+1][min(j+k+1,X)][k+1][5] += t;
            dp[i+1][min(j+k+1,X)][k+1][5] %= mod;
            continue;
          }
          if(l == 5 and S[i] == '2'){
            dp[i+1][j][k][2] += t;
            dp[i+1][j][k][2] %= mod;
            continue;
          }
          dp[i+1][j][0][S[i]-'0'] += t;
          dp[i+1][j][0][S[i]-'0'] %= mod;
        }
      }
    }
  }
  long long ans = 0;
  for(int i = 0; i < 130; ++i){
    for(int k = 0; k < 10; ++k){
      ans += dp[N][X][i][k];
      ans %= mod;
    }
  }
  cout << ans << endl;
}

Submission

Task問題 A - ニコニコ文字列2
User nameユーザ名 TAB
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 MLE
Score得点 0
Source lengthソースコード長 1601 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 0 / 20 sample_01.txt,sample_02.txt,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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 2 ms 6400 KB
sample_02.txt AC 7 ms 30976 KB
subtask1_01.txt AC 2 ms 2304 KB
subtask1_02.txt AC 2 ms 4352 KB
subtask1_03.txt AC 2 ms 4352 KB
subtask1_04.txt AC 2 ms 2304 KB
subtask1_05.txt MLE
subtask1_06.txt MLE
subtask1_07.txt MLE
subtask1_08.txt AC 58 ms 157952 KB
subtask1_09.txt AC 39 ms 149760 KB
subtask1_10.txt AC 22 ms 88320 KB
subtask1_11.txt MLE
subtask1_12.txt MLE
subtask1_13.txt MLE
subtask1_14.txt MLE
subtask1_15.txt MLE
subtask1_16.txt MLE
subtask1_17.txt MLE
subtask1_18.txt MLE
subtask1_19.txt MLE
subtask1_20.txt MLE
subtask1_21.txt MLE
subtask1_22.txt MLE