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

Submission #4030450

Source codeソースコード

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007, N = 200000, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };

ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}
struct ab {
	ll a, b;
	bool operator<(const ab& right) const {
		return right.b*a - right.a*b < 0;
	}
};

/*
void src(ll v, ll d[]) {
priority_queue<pos> q;
q.push(make_pair(0, v));
while (!q.empty()) {
ll ci = q.top().second, cd = -q.top().first;
q.pop();
if (d[ci] != -1)continue; d[ci] = cd;
for (int i = 0; i < G[ci].size(); i++) {
ll ni = G[ci][i].second, nd = cd + G[ci][i].first;
if (d[ni] != -1)continue;
q.push(make_pair(-nd, ni));
}
}
}
*/

ll n, x, dp[254][254][254];//index x_count niconico

int main() {
	cin >> n >> x;
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		char v1; cin >> v1;
		if (v1 == '?') {
			for (ll j = 0; j <= 252; j++) {
				for (int k = 0; k <= 252; k++) {
					if (dp[i][j][k] == 0)continue;
					if (k % 2 == 1) {
						//add 5 
						dp[i + 1][min(x,j + k / 2 + 1)][k + 1] = (dp[i + 1][min(x, j + k / 2 + 1)][k + 1] + dp[i][j][k]) % MOD;
						//add 2
						dp[i + 1][j][1] = (dp[i + 1][j][1]+dp[i][j][k])%MOD;

						dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k] * 8) % MOD;
					}
					else {
						dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]*9) % MOD;
						dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD;
					}
				}
			}
		}
		else {
			for (ll j = 0; j <= 252; j++) {
				for (int k = 0; k <= 252; k++) {
					if (dp[i][j][k] == 0)continue;
					if (k % 2 == 1 && v1 == '5') {
						dp[i + 1][min(x, j + k / 2 + 1)][k + 1] = (dp[i + 1][min(x, j + k / 2 + 1)][k + 1] + dp[i][j][k]) % MOD;
					}
					else if (v1 == '2') {
						if(k%2==0)dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD;
						else dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][k]) % MOD;
					}
					else {
						dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]) % MOD;
					}
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= 252; i++)ans = (ans + dp[n][x][i]) % MOD;
	cout << ans << endl;
	return 0;
}

Submission

Task問題 A - ニコニコ文字列2
User nameユーザ名 J190563HN
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 20
Source lengthソースコード長 2493 Byte
File nameファイル名
Exec time実行時間 49 ms
Memory usageメモリ使用量 125696 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 256 KB
sample_02.txt AC 3 ms 6400 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 27 ms 90368 KB
subtask1_06.txt AC 21 ms 69888 KB
subtask1_07.txt AC 20 ms 65792 KB
subtask1_08.txt AC 11 ms 30976 KB
subtask1_09.txt AC 11 ms 30976 KB
subtask1_10.txt AC 7 ms 18688 KB
subtask1_11.txt AC 37 ms 125184 KB
subtask1_12.txt AC 38 ms 125312 KB
subtask1_13.txt AC 38 ms 125184 KB
subtask1_14.txt AC 38 ms 125440 KB
subtask1_15.txt AC 39 ms 125440 KB
subtask1_16.txt AC 39 ms 125440 KB
subtask1_17.txt AC 49 ms 125696 KB
subtask1_18.txt AC 37 ms 125184 KB
subtask1_19.txt AC 45 ms 125696 KB
subtask1_20.txt AC 39 ms 125440 KB
subtask1_21.txt AC 38 ms 125184 KB
subtask1_22.txt AC 37 ms 125184 KB