Typical DP Contest

Submission #782853

Source codeソースコード

#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

Task問題 F - 準急
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 1221 Byte
File nameファイル名
Exec time実行時間 64 ms
Memory usageメモリ使用量 16416 KB

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,03,04,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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