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

Submission #4066135

Source codeソースコード

// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

const int LEN = 300;
const int SQRT = 24;

int calc(int x) {
    return x * (x + 1) / 2;
}

// (252, 252, 24, 100)
int dp[2][LEN][SQRT][100];
signed main() {
    int N, X; cin >> N >> X;

    string s; cin >> s;
    s += "0"; N++;

    dp[0][0][0][0] = 1;
    for(int i=0; i<N; i++) {
        int cur = i % 2, nxt = 1 - cur;
        for(int j=0; j<=X; j++) {
            for(int k=0; k<SQRT; k++) {
                for(int d=0; d<100; d++) {
                    if(dp[cur][j][k][d] == 0) continue;
                    for(int x=0; x<10; x++) {
                        if(s[i] != '?' and s[i] - '0' != x) continue;
                        int nd = (d * 10 + x) % 100, nj = j, nk = k;
                        if(nd == 25) nk++;
                        else if(nd != 52) nj = min(X, j + calc(k)), nk = 0;

                        (dp[nxt][nj][nk][nd] += dp[cur][j][k][d]) %= MOD;
                    }
                    dp[cur][j][k][d] = 0;
                }
            }
        }
    }

    int ans = 0;
    for(int i=0; i<100; i++) (ans += dp[N%2][X][0][i]) %= MOD;
    cout << ans << endl;
    return 0;
}

Submission

Task問題 A - ニコニコ文字列2
User nameユーザ名 tsutaj
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2148 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 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 5 ms 2304 KB
subtask1_06.txt AC 26 ms 4736 KB
subtask1_07.txt WA
subtask1_08.txt WA
subtask1_09.txt AC 27 ms 5504 KB
subtask1_10.txt AC 11 ms 4992 KB
subtask1_11.txt AC 9 ms 2304 KB
subtask1_12.txt AC 148 ms 4608 KB
subtask1_13.txt AC 9 ms 2432 KB
subtask1_14.txt AC 156 ms 9344 KB
subtask1_15.txt WA
subtask1_16.txt WA
subtask1_17.txt WA
subtask1_18.txt AC 144 ms 2304 KB
subtask1_19.txt WA
subtask1_20.txt WA
subtask1_21.txt WA
subtask1_22.txt WA