結果
問題 | No.1011 Infinite Stairs |
ユーザー | yoshig0731 |
提出日時 | 2020-04-29 17:31:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 4,409 bytes |
コンパイル時間 | 1,934 ms |
コンパイル使用メモリ | 79,748 KB |
実行使用メモリ | 215,076 KB |
最終ジャッジ日時 | 2023-09-24 11:14:21 |
合計ジャッジ時間 | 2,770 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,348 KB |
testcase_01 | AC | 2 ms
7,388 KB |
testcase_02 | AC | 36 ms
149,468 KB |
testcase_03 | AC | 97 ms
187,604 KB |
testcase_04 | AC | 46 ms
156,752 KB |
testcase_05 | AC | 131 ms
215,076 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 25 ms
113,976 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
5,336 KB |
testcase_10 | AC | 12 ms
52,588 KB |
testcase_11 | AC | 46 ms
155,716 KB |
testcase_12 | AC | 11 ms
50,480 KB |
testcase_13 | AC | 29 ms
104,004 KB |
testcase_14 | AC | 14 ms
64,804 KB |
testcase_15 | AC | 41 ms
149,916 KB |
testcase_16 | AC | 77 ms
171,152 KB |
testcase_17 | AC | 35 ms
151,508 KB |
testcase_18 | AC | 52 ms
147,676 KB |
testcase_19 | AC | 9 ms
38,280 KB |
testcase_20 | AC | 9 ms
38,128 KB |
testcase_21 | AC | 30 ms
96,260 KB |
testcase_22 | AC | 53 ms
155,272 KB |
testcase_23 | AC | 29 ms
85,948 KB |
testcase_24 | AC | 36 ms
114,432 KB |
testcase_25 | AC | 55 ms
155,752 KB |
testcase_26 | AC | 19 ms
67,100 KB |
ソースコード
#include <algorithm> #include <cstdint> #include <cstring> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, s, t) for (int i = s; i < t; i++) #define ALL(obj) obj.begin(), obj.end() const int iINF = 1e9; const long long llINF = 1e18; const int MOD = 1e9 + 7; template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template <int MOD> struct ModInt { long long val; constexpr ModInt(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD; } constexpr ModInt operator-() const noexcept { return val ? MOD - val : 0; } constexpr ModInt operator+(const ModInt& r) const noexcept { return ModInt(*this) += r; } constexpr ModInt operator-(const ModInt& r) const noexcept { return ModInt(*this) -= r; } constexpr ModInt operator*(const ModInt& r) const noexcept { return ModInt(*this) *= r; } constexpr ModInt operator/(const ModInt& r) const noexcept { return ModInt(*this) /= r; } constexpr ModInt& operator+=(const ModInt& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr ModInt& operator-=(const ModInt& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr ModInt& operator*=(const ModInt& r) noexcept { val = val * r.val % MOD; return *this; } constexpr ModInt& operator/=(const ModInt& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator==(const ModInt& r) const noexcept { return this->val == r.val; } constexpr bool operator!=(const ModInt& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator<<(ostream& os, const ModInt<MOD>& x) noexcept { return os << x.val; } friend constexpr istream& operator>>(istream& is, ModInt<MOD>& x) noexcept { return is >> x.val; } friend constexpr ModInt<MOD> modpow(const ModInt<MOD>& a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; using mint = ModInt<MOD>; long long modPow(long long x, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } long long extGCD(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } long long gcd(long long a, long long b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; } template <typename T> map<T, int> compress(vector<T> x) { map<T, int> res; sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); for (int i = 0; i < x.size(); i++) { res[x[i]] = i; } return res; } template <typename T> int former(const vector<T>& v, T x) { return upper_bound(v.begin(), v.end(), x) - v.begin() - 1; } template <typename T> int latter(const vector<T>& v, T x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); } template <typename T> using Vec = vector<T>; template <typename T> using VVec = vector<vector<T>>; using LL = long long; mint dp[310][90010]; int main() { int N, d, K; cin >> N >> d >> K; dp[0][0] = 1; FOR(i, 1, N + 1) { mint sum[K + 1]; memset(sum, 0, sizeof(sum)); REP(j, K) sum[j + 1] = sum[j] + dp[i - 1][j]; REP(j, K + 1) { dp[i][j] = sum[j] - sum[max(0, j - d)]; } } cout << dp[N][K] << endl; return 0; }