Submission #1058918
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;
vvi dp(601, vi(601, 0)); // i番目まで、suffixのminがjでmaxがlであるパターンの数
dp[300][300] = 1;
rep (i, n) {
vvi tmp(601, vi(601, 0));
switch (s[i]) {
case '0':
FOR (j, 300-k, 301+k) {
FOR (l, j, 301+k) {
if (l+1 <= 300+k) {
tmp[min(301, j+1)][max(301, l+1)] += dp[j][l];
tmp[min(301, j+1)][max(301, l+1)] %= mod;
}
}
}
dp = tmp;
break;
case '1':
FOR (j, 300-k, 301+k) {
FOR (l, j, 301+k) {
if (j-1 >= 300-k) {
tmp[min(299, j-1)][max(299, l-1)] += dp[j][l];
tmp[min(299, j-1)][max(299, l-1)] %= mod;
}
}
}
dp = tmp;
break;
case '?':
FOR (j, 300-k, 301+k) {
FOR (l, j, 301+k) {
if (l+1 <= 300+k) {
tmp[min(301, j+1)][max(301, l+1)] += dp[j][l];
tmp[min(301, j+1)][max(301, l+1)] %= mod;
}
if (j-1 >= 300-k) {
tmp[min(299, j-1)][max(299, l-1)] += dp[j][l];
tmp[min(299, j-1)][max(299, l-1)] %= mod;
}
}
}
dp = tmp;
break;
}
}
int ans = 0;
FOR (j, 300-k, 301+k) {
FOR (l, j, 301+k) {
ans += dp[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 |
2379 Byte |
Status |
AC |
Exec Time |
1064 ms |
Memory |
3776 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 |
39 ms |
3660 KB |
subtask0-sample-02.txt |
AC |
37 ms |
3772 KB |
subtask0-sample-03.txt |
AC |
36 ms |
3648 KB |
subtask0-sample-04.txt |
AC |
43 ms |
3764 KB |
subtask1-01.txt |
AC |
22 ms |
3616 KB |
subtask1-02.txt |
AC |
28 ms |
3744 KB |
subtask1-03.txt |
AC |
40 ms |
3776 KB |
subtask1-04.txt |
AC |
43 ms |
3740 KB |
subtask1-05.txt |
AC |
44 ms |
3692 KB |
subtask1-06.txt |
AC |
43 ms |
3744 KB |
subtask1-07.txt |
AC |
43 ms |
3744 KB |
subtask1-08.txt |
AC |
42 ms |
3696 KB |
subtask1-09.txt |
AC |
42 ms |
3692 KB |
subtask1-10.txt |
AC |
43 ms |
3692 KB |
subtask2-01.txt |
AC |
245 ms |
3740 KB |
subtask2-02.txt |
AC |
361 ms |
3692 KB |
subtask2-03.txt |
AC |
580 ms |
3772 KB |
subtask2-04.txt |
AC |
587 ms |
3772 KB |
subtask2-05.txt |
AC |
586 ms |
3736 KB |
subtask2-06.txt |
AC |
584 ms |
3740 KB |
subtask2-07.txt |
AC |
587 ms |
3672 KB |
subtask2-08.txt |
AC |
584 ms |
3692 KB |
subtask2-09.txt |
AC |
582 ms |
3744 KB |
subtask2-10.txt |
AC |
587 ms |
3744 KB |
subtask3-01.txt |
AC |
491 ms |
3696 KB |
subtask3-02.txt |
AC |
592 ms |
3656 KB |
subtask3-03.txt |
AC |
580 ms |
3736 KB |
subtask3-04.txt |
AC |
591 ms |
3736 KB |
subtask3-05.txt |
AC |
586 ms |
3740 KB |
subtask3-06.txt |
AC |
587 ms |
3656 KB |
subtask3-07.txt |
AC |
1064 ms |
3744 KB |
subtask3-08.txt |
AC |
581 ms |
3740 KB |
subtask3-09.txt |
AC |
584 ms |
3740 KB |
subtask3-10.txt |
AC |
586 ms |
3696 KB |