Submission #5494862
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> Pint; typedef pair<ll, ll> P; //typedef pair<int, pair<int, int>> P; //typedef tuple<int,int,int> T; ll INFL = 1000000000000000010;//10^18 = 2^60 int INF = 2147483600;//10^9 ll MOD = 1000000007; vector<int> dy = {0,0,1,-1}; vector<int> dx = {1,-1,0,0}; int N,K; vector<vector<ll>> dp(1000010, vector<ll>(2, 0)); int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K; dp[0][0] = 1; dp[1][1] = 1; for(int i = 2; i <= N; i++){ dp[i][0] = dp[i-1][0] + dp[i-1][1];//天才 dp[i][0] %= MOD; dp[i][1] = dp[i-1][0] + dp[i-1][1]; if(i-K >= 0){ dp[i][1] -= dp[i-K][0];//ちょうどK連続だけを引く } dp[i][1] += MOD; dp[i][1] %= MOD; } cout << dp[N][1] << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - 準急 |
User | shogier |
Language | C++14 (GCC 5.4.1) |
Score | 4 |
Code Size | 904 Byte |
Status | AC |
Exec Time | 82 ms |
Memory | 54912 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 4 / 4 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 82 ms | 54912 KB |
01 | AC | 82 ms | 54912 KB |
02 | AC | 70 ms | 54912 KB |
03 | AC | 66 ms | 54912 KB |
04 | AC | 81 ms | 54912 KB |
90 | AC | 60 ms | 54912 KB |
91 | AC | 60 ms | 54912 KB |