Submission #1513004
Source Code Expand
#include <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))
using namespace std;
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
// Problem Specific Parameter:
const ll mod=1000000007LL;
ll dp[3010][3010][2];
int main(void){
ll n,m;
cin >> n >> m;
rep(i,n+1) dp[0][i][(i==0)]=1LL;
rep(i,m)rep(j,n+1)rep(k,2){
dp[i][j][k]%=mod;
if(j-1>=0){
int nk = k;
if(j==1) nk = 1;
dp[i+1][j-1][nk] += dp[i][j][k];
dp[i+1][j][nk] += dp[i][j][k];
}
if(j+1<=n){
const int nk = k;
dp[i+1][j][nk] += dp[i][j][k];
dp[i+1][j+1][nk] += dp[i][j][k];
}
}
ll ans=0LL;
rep(i,n+1) ans=(ans+dp[m][i][1])%mod;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Piling Up |
User |
Hec |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
1730 Byte |
Status |
AC |
Exec Time |
120 ms |
Memory |
141568 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
512 KB |
sample_03.txt |
AC |
58 ms |
140416 KB |
subtask_1_01.txt |
AC |
21 ms |
28800 KB |
subtask_1_02.txt |
AC |
16 ms |
54016 KB |
subtask_1_03.txt |
AC |
51 ms |
140160 KB |
subtask_1_04.txt |
AC |
39 ms |
77184 KB |
subtask_1_05.txt |
AC |
89 ms |
120832 KB |
subtask_1_06.txt |
AC |
51 ms |
140160 KB |
subtask_1_07.txt |
AC |
54 ms |
130176 KB |
subtask_1_08.txt |
AC |
26 ms |
90752 KB |
subtask_1_09.txt |
AC |
88 ms |
141056 KB |
subtask_1_10.txt |
AC |
120 ms |
141568 KB |
subtask_1_11.txt |
AC |
49 ms |
128000 KB |
subtask_1_12.txt |
AC |
32 ms |
80896 KB |
subtask_1_13.txt |
AC |
48 ms |
140160 KB |
subtask_1_14.txt |
AC |
32 ms |
119424 KB |
subtask_1_15.txt |
AC |
17 ms |
41984 KB |
subtask_1_16.txt |
AC |
56 ms |
140288 KB |
subtask_1_17.txt |
AC |
22 ms |
68352 KB |
subtask_1_18.txt |
AC |
24 ms |
58496 KB |
subtask_1_19.txt |
AC |
38 ms |
139904 KB |
subtask_1_20.txt |
AC |
58 ms |
140416 KB |
subtask_1_21.txt |
AC |
11 ms |
55680 KB |
subtask_1_22.txt |
AC |
28 ms |
139648 KB |
subtask_1_23.txt |
AC |
14 ms |
70016 KB |
subtask_1_24.txt |
AC |
28 ms |
139648 KB |
subtask_1_25.txt |
AC |
1 ms |
384 KB |
subtask_1_26.txt |
AC |
27 ms |
139648 KB |
subtask_1_27.txt |
AC |
1 ms |
256 KB |