Submission #1502579


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

ll dp[3010][3010 + 100][2];

int main() {
	int n, m;
	cin >> n >> m;
	dp[0][0][1] = 1LL;
	rep(i, n) dp[0][i + 1][0] = 1LL;

	rep(i, m) {
		rep(j, 3010) {
			if (j == 0) {
				if (j < n) {
					// blue -> red
					(dp[i + 1][0][1] += dp[i][0][1]) %= MOD;
					// blue -> blue
					(dp[i + 1][1][1] += dp[i][0][1]) %= MOD;
				}
			} else if (j == 1) {
				// red -> red
				(dp[i + 1][0][1] += dp[i][1][0] + dp[i][1][1]) %= MOD;

				// red -> blue
				(dp[i + 1][1][1] += dp[i][1][0] + dp[i][1][1]) %= MOD;

				// blue -> red
				if (j < n) {
					(dp[i + 1][1][0] += dp[i][1][0]) %= MOD;
					(dp[i + 1][1][1] += dp[i][1][1]) %= MOD;

					// blue -> blue
					(dp[i + 1][2][0] += dp[i][1][0]) %= MOD;
					(dp[i + 1][2][1] += dp[i][1][1]) %= MOD;
				}
			} else {
				// red -> red
				(dp[i + 1][j - 1][0] += dp[i][j][0]) %= MOD;
				(dp[i + 1][j - 1][1] += dp[i][j][1]) %= MOD;

				// red -> blue
				(dp[i + 1][j][0] += dp[i][j][0]) %= MOD;
				(dp[i + 1][j][1] += dp[i][j][1]) %= MOD;

				if (j < n) {
					// blue -> red
					(dp[i + 1][j][0] += dp[i][j][0]) %= MOD;
					(dp[i + 1][j][1] += dp[i][j][1]) %= MOD;

					// blue -> blue
					(dp[i + 1][j + 1][0] += dp[i][j][0]) %= MOD;
					(dp[i + 1][j + 1][1] += dp[i][j][1]) %= MOD;
				}
			}
		}
	}
	// rep(i, n+1) cout << " " << dp[m][i][1];
	// cout << endl;
	ll ans = 0LL;
	rep(i, n + 1) (ans += dp[m][i][1]) %= MOD;
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Piling Up
User T1610
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2040 Byte
Status AC
Exec Time 153 ms
Memory 146048 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 384 KB
sample_02.txt AC 2 ms 768 KB
sample_03.txt AC 116 ms 146048 KB
subtask_1_01.txt AC 29 ms 28928 KB
subtask_1_02.txt AC 42 ms 57472 KB
subtask_1_03.txt AC 112 ms 146048 KB
subtask_1_04.txt AC 68 ms 80128 KB
subtask_1_05.txt AC 123 ms 125184 KB
subtask_1_06.txt AC 112 ms 146048 KB
subtask_1_07.txt AC 108 ms 137472 KB
subtask_1_08.txt AC 69 ms 96512 KB
subtask_1_09.txt AC 134 ms 146048 KB
subtask_1_10.txt AC 153 ms 146048 KB
subtask_1_11.txt AC 104 ms 135424 KB
subtask_1_12.txt AC 66 ms 84224 KB
subtask_1_13.txt AC 110 ms 146048 KB
subtask_1_14.txt AC 89 ms 125056 KB
subtask_1_15.txt AC 36 ms 45312 KB
subtask_1_16.txt AC 115 ms 146048 KB
subtask_1_17.txt AC 53 ms 71936 KB
subtask_1_18.txt AC 49 ms 61696 KB
subtask_1_19.txt AC 104 ms 146048 KB
subtask_1_20.txt AC 116 ms 146048 KB
subtask_1_21.txt AC 40 ms 59520 KB
subtask_1_22.txt AC 97 ms 146048 KB
subtask_1_23.txt AC 50 ms 73856 KB
subtask_1_24.txt AC 97 ms 146048 KB
subtask_1_25.txt AC 3 ms 1792 KB
subtask_1_26.txt AC 97 ms 146048 KB
subtask_1_27.txt AC 1 ms 256 KB