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

Submission #4063870

Source codeソースコード

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

long long dp[2][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%2][j][k][l];
          dp[i%2][j][k][l] = 0;
          if(t == 0) continue;
          if(S[i] == '?'){
            for(int m = 0; m < 10; ++m){
              if(l == 5 and m == 2){
                dp[(i+1)%2][j][k][m] += t;
                dp[(i+1)%2][j][k][m] %= mod;
                continue;
              }
              if(l == 2 and m == 5){
                dp[(i+1)%2][min(j+k+1,X)][k+1][m] += t;
                dp[(i+1)%2][min(j+k+1,X)][k+1][m] %= mod;
                continue;
              }
              dp[(i+1)%2][j][0][m] += t;
              dp[(i+1)%2][j][0][m] %= mod;
            }
            continue;
          }
          if(l == 2 and S[i] == '5'){
            dp[(i+1)%2][min(j+k+1,X)][k+1][5] += t;
            dp[(i+1)%2][min(j+k+1,X)][k+1][5] %= mod;
            continue;
          }
          if(l == 5 and S[i] == '2'){
            dp[(i+1)%2][j][k][2] += t;
            dp[(i+1)%2][j][k][2] %= mod;
            continue;
          }
          dp[(i+1)%2][j][0][S[i]-'0'] += t;
          dp[(i+1)%2][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%2][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状態 AC
Score得点 20
Source lengthソースコード長 1684 Byte
File nameファイル名
Exec time実行時間 160 ms
Memory usageメモリ使用量 5376 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 20 / 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 2304 KB
sample_02.txt AC 2 ms 2304 KB
subtask1_01.txt AC 2 ms 2304 KB
subtask1_02.txt AC 2 ms 2304 KB
subtask1_03.txt AC 2 ms 2304 KB
subtask1_04.txt AC 2 ms 2304 KB
subtask1_05.txt AC 4 ms 2304 KB
subtask1_06.txt AC 18 ms 2944 KB
subtask1_07.txt AC 8 ms 2560 KB
subtask1_08.txt AC 31 ms 5120 KB
subtask1_09.txt AC 11 ms 3072 KB
subtask1_10.txt AC 6 ms 2944 KB
subtask1_11.txt AC 7 ms 2432 KB
subtask1_12.txt AC 105 ms 5376 KB
subtask1_13.txt AC 6 ms 2432 KB
subtask1_14.txt AC 106 ms 5376 KB
subtask1_15.txt AC 107 ms 5376 KB
subtask1_16.txt AC 107 ms 5376 KB
subtask1_17.txt AC 160 ms 5376 KB
subtask1_18.txt AC 104 ms 5376 KB
subtask1_19.txt AC 146 ms 5376 KB
subtask1_20.txt AC 108 ms 5376 KB
subtask1_21.txt AC 3 ms 2304 KB
subtask1_22.txt AC 2 ms 2304 KB