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 |
|
|
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 |