Submission #1058696
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
int mod = 1e9 + 7;
int main() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
//vv<vi> dp(n+1, vvi(601, vi(601, 0))); // i番目まで、suffixのminがjでmaxがlであるパターンの数
vv<vi> dp(n+1); // i番目まで、suffixのminがjでmaxがlであるパターンの数
rep (i, n+1) {
dp[i].assign(i*2+1, vi(i*2+1, 0));
}
dp[0][0][0] = 1;
//int mini, maxi, mini_, maxi_, j_, l_;
int j_, l_;
rep (i, n) {
/*
mini = max(0, (i-k+1)/2);
maxi = min(i, (i+k)/2);
mini_ = max(0, (i-k+2)/2);
maxi_ = min(i+1, (i+1+k)/2);
*/
switch (s[i]) {
case '0':
FOR (j, max(0, i-k), min(i*2, i+k) + 1) {
FOR (l, j, min(i*2, i+k) + 1) {
j_ = min(i+2, j+2);
l_ = max(i+2, l+2);
if (i+1-k <= j_ && l_ <= i+1+k) {
dp[i+1][j_][l_] += dp[i][j][l];
dp[i+1][j_][l_] %= mod;
}
}
}
break;
case '1':
FOR (j, max(0, i-k), min(i*2, i+k) + 1) {
FOR (l, j, min(i*2, i+k) + 1) {
j_ = min(i, j);
l_ = max(i, l);
if (i+1-k <= j_ && l_ <= i+1+k) {
dp[i+1][j_][l_] += dp[i][j][l];
dp[i+1][j_][l_] %= mod;
}
}
}
break;
case '?':
FOR (j, max(0, i-k), min(i*2, i+k) + 1) {
FOR (l, j, min(i*2, i+k) + 1) {
j_ = min(i+2, j+2);
l_ = max(i+2, l+2);
if (i+1-k <= j_ && l_ <= i+1+k) {
dp[i+1][j_][l_] += dp[i][j][l];
dp[i+1][j_][l_] %= mod;
}
j_ = min(i, j);
l_ = max(i, l);
if (i+1-k <= j_ && l_ <= i+1+k) {
dp[i+1][j_][l_] += dp[i][j][l];
dp[i+1][j_][l_] %= mod;
}
}
}
break;
}
}
int ans = 0;
FOR (j, max(0, n-k), min(n*2, n+k) + 1) {
FOR (l, j, min(n*2, n+k) + 1) {
ans += dp[n][j][l];
ans %= mod;
}
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 偶然ジェネレータ |
User |
tspcx |
Language |
C++14 (Clang++ 3.4) |
Score |
100 |
Code Size |
2949 Byte |
Status |
AC |
Exec Time |
444 ms |
Memory |
146548 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
10 / 10 |
30 / 30 |
60 / 60 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask0-sample-04.txt |
Subtask1 |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask0-sample-04.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 |
Subtask2 |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask0-sample-04.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt |
Subtask3 |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask0-sample-04.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, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0-sample-01.txt |
AC |
17 ms |
796 KB |
subtask0-sample-02.txt |
AC |
17 ms |
924 KB |
subtask0-sample-03.txt |
AC |
18 ms |
796 KB |
subtask0-sample-04.txt |
AC |
17 ms |
796 KB |
subtask1-01.txt |
AC |
19 ms |
796 KB |
subtask1-02.txt |
AC |
18 ms |
800 KB |
subtask1-03.txt |
AC |
19 ms |
924 KB |
subtask1-04.txt |
AC |
17 ms |
800 KB |
subtask1-05.txt |
AC |
17 ms |
800 KB |
subtask1-06.txt |
AC |
17 ms |
920 KB |
subtask1-07.txt |
AC |
17 ms |
796 KB |
subtask1-08.txt |
AC |
16 ms |
800 KB |
subtask1-09.txt |
AC |
17 ms |
796 KB |
subtask1-10.txt |
AC |
19 ms |
920 KB |
subtask2-01.txt |
AC |
33 ms |
10656 KB |
subtask2-02.txt |
AC |
71 ms |
33016 KB |
subtask2-03.txt |
AC |
250 ms |
146464 KB |
subtask2-04.txt |
AC |
250 ms |
146464 KB |
subtask2-05.txt |
AC |
251 ms |
146472 KB |
subtask2-06.txt |
AC |
248 ms |
146544 KB |
subtask2-07.txt |
AC |
250 ms |
146548 KB |
subtask2-08.txt |
AC |
251 ms |
146464 KB |
subtask2-09.txt |
AC |
249 ms |
146548 KB |
subtask2-10.txt |
AC |
252 ms |
146464 KB |
subtask3-01.txt |
AC |
159 ms |
85748 KB |
subtask3-02.txt |
AC |
258 ms |
146464 KB |
subtask3-03.txt |
AC |
251 ms |
146548 KB |
subtask3-04.txt |
AC |
249 ms |
146464 KB |
subtask3-05.txt |
AC |
252 ms |
146456 KB |
subtask3-06.txt |
AC |
257 ms |
146528 KB |
subtask3-07.txt |
AC |
444 ms |
146540 KB |
subtask3-08.txt |
AC |
249 ms |
146472 KB |
subtask3-09.txt |
AC |
250 ms |
146548 KB |
subtask3-10.txt |
AC |
253 ms |
146528 KB |