Submission #1534110


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = 1e9 + 7;

ll dp[3005][3005], ans[3005];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	ll ans = 0;
	for (int lim = n; lim >= n - 1; lim--) {
		for (int i = 0; i <= lim; i++) dp[0][i] = 1;
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j <= lim; j++) {
				dp[i][j] = 0;
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j <= lim; j++) {
				if (j > 0) {
					(dp[i + 1][j] += dp[i][j]) %= MOD;
					(dp[i + 1][j - 1] += dp[i][j]) %= MOD;
				}
				if (j < lim) {
					(dp[i + 1][j] += dp[i][j]) %= MOD;
					(dp[i + 1][j + 1] += dp[i][j]) %= MOD;
				}
			}
		}	

		for (int i = 0; i <= lim; i++) {
			if (lim == n) (ans += dp[m][i]) %= MOD;
			else (ans += (MOD - dp[m][i]) % MOD) %= MOD;
		}	
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Piling Up
User fine
Language C++14 (GCC 5.4.1)
Score 900
Code Size 914 Byte
Status AC
Exec Time 497 ms
Memory 70656 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 2 ms 384 KB
sample_03.txt AC 176 ms 69248 KB
subtask_1_01.txt AC 82 ms 14592 KB
subtask_1_02.txt AC 33 ms 27520 KB
subtask_1_03.txt AC 138 ms 69120 KB
subtask_1_04.txt AC 135 ms 38400 KB
subtask_1_05.txt AC 355 ms 61696 KB
subtask_1_06.txt AC 139 ms 69120 KB
subtask_1_07.txt AC 160 ms 64768 KB
subtask_1_08.txt AC 53 ms 45952 KB
subtask_1_09.txt AC 326 ms 70144 KB
subtask_1_10.txt AC 497 ms 70656 KB
subtask_1_11.txt AC 139 ms 64640 KB
subtask_1_12.txt AC 94 ms 40192 KB
subtask_1_13.txt AC 124 ms 68992 KB
subtask_1_14.txt AC 59 ms 60288 KB
subtask_1_15.txt AC 47 ms 21632 KB
subtask_1_16.txt AC 166 ms 69248 KB
subtask_1_17.txt AC 54 ms 33792 KB
subtask_1_18.txt AC 73 ms 29952 KB
subtask_1_19.txt AC 71 ms 68736 KB
subtask_1_20.txt AC 176 ms 69248 KB
subtask_1_21.txt AC 7 ms 27264 KB
subtask_1_22.txt AC 15 ms 68352 KB
subtask_1_23.txt AC 8 ms 35456 KB
subtask_1_24.txt AC 14 ms 68352 KB
subtask_1_25.txt AC 1 ms 384 KB
subtask_1_26.txt AC 15 ms 68352 KB
subtask_1_27.txt AC 1 ms 256 KB