Submission #1180541


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 1000000007LL
#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][0] = 1;
  dp[1][1] = 1;
  reps(i, 2, n+1) {
    dp[0][i] = (dp[0][i-1] + dp[1][i-1]) % CONST;
    dp[1][i] = (dp[0][i-1] + dp[1][i-1]) % CONST;
    if(i-k+1 >= 0) {
      dp[1][i] += (CONST - dp[0][i-k+1]);
      dp[1][i] %= CONST;
    }
  }
  assert(dp[1][n] > 0);
  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 1317 Byte
Status WA
Exec Time 15 ms
Memory 15872 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 2
WA × 5
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 WA 15 ms 15872 KB
01 AC 11 ms 15872 KB
02 WA 8 ms 10496 KB
03 WA 7 ms 10496 KB
04 WA 14 ms 15232 KB
90 WA 2 ms 2304 KB
91 AC 2 ms 2304 KB