Submission #1180523
Source Code Expand
// http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp
#include<bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef long long ll;
typedef pair<ll,ll> P;
const int INF=INT_MAX / 3;
const ll LINF=LLONG_MAX / 3LL;
#define CONST 1000000007
#define EPS (1e-8)
#define PB push_back
#define MP make_pair
#define sz(a) ((int)(a).size())
#define reps(i,n,m) for(int i=(n);i<int(m);i++)
#define rep(i,n) reps(i,0,n)
#define SORT(a) sort((a).begin(),(a).end())
ll mod(ll a,ll m){return (a%m+m)%m;}
int dx[9]={0,1,0,-1,1,1,-1,-1,0},dy[9]={1,0,-1,0,1,-1,1,-1,0};
ll n,m, k;
/*
dp[0][i] = {i番目の駅に止まらない場合の数}
dp[1][i] = {i番目の駅に止まる場合の数}
参考: http://kenkoooo.hatenablog.com/entry/2015/03/24/152721
*/
ll dp[2][1000100];
int main(){
cin >> n >> k;
dp[0][1] = 0;
dp[1][1] = 1;
reps(i, 2, n+1) {
dp[0][i] = dp[0][i-1] + dp[1][i-1];
dp[1][i] = dp[0][i-1] + dp[1][i-1] - dp[0][i+1-k];
}
cout << dp[1][n] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - 準急 |
User |
udondon |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1187 Byte |
Status |
RE |
Exec Time |
96 ms |
Memory |
15872 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 4 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
WA |
6 ms |
15872 KB |
01 |
RE |
96 ms |
2304 KB |
02 |
RE |
96 ms |
2304 KB |
03 |
RE |
96 ms |
2304 KB |
04 |
WA |
6 ms |
15232 KB |
90 |
WA |
2 ms |
2304 KB |
91 |
WA |
2 ms |
2304 KB |