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
WA × 4
RE × 3
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