Submission #782853


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int mod=1e9+7;

int dp[1000001][2]={0};
int sum[1000001][2]={0};

int main()
{
    int n,k;
    cin >>n >>k;

    //初期化
    dp[0][0]=sum[0][0]=1;
    dp[0][1]=sum[0][1]=0;

    for(int i=1; i<=n; ++i)
    {
        //この区間が0:don't stop
        //iを区間の終点として,区間はいくらでも長く出来る
        dp[i][0]=sum[i-1][1];

        //前の区間が1:stop
        //iを区間の終点として連続でk-1駅まで止まれる
        dp[i][1]=sum[i-1][0];
        if(i-k>=0)
        {
            dp[i][1]-=sum[i-k][0];
            dp[i][1]=(dp[i][1]+mod)%mod;
        }

        //sumを更新
        sum[i][0]=(sum[i-1][0]+dp[i][0])%mod;
        sum[i][1]=(sum[i-1][1]+dp[i][1])%mod;
    }

    //rep(i,n+1)rep(j,2) printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);

    cout << dp[n][1] << endl;
    return 0;
}

Submission Info

Submission Time
Task F - 準急
User imulan
Language C++11 (GCC 4.8.1)
Score 4
Code Size 1221 Byte
Status AC
Exec Time 64 ms
Memory 16416 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 64 ms 16416 KB
01 AC 60 ms 16416 KB
02 AC 42 ms 7840 KB
03 AC 38 ms 5800 KB
04 AC 62 ms 15136 KB
90 AC 23 ms 800 KB
91 AC 23 ms 800 KB