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
AC × 3
AC × 33
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