結果

問題 No.801 エレベーター
コンテスト
ユーザー betrue12
提出日時 2019-03-17 21:58:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 245 ms / 2,000 ms
コード長 804 bytes
コンパイル時間 2,118 ms
コンパイル使用メモリ 194,368 KB
最終ジャッジ日時 2025-01-06 22:59:52
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}


int main(){
    int N, M, K, L[3000], R[3000];
    cin >> N >> M >> K;
    for(int i=0; i<M; i++){
        cin >> L[i] >> R[i];
    }

    static int64_t dp[3001][3002];

    dp[0][1] = 1;
    for(int i=0; i<K; i++){
        int64_t sum[3001] = {0};
        for(int j=1; j<=N; j++){
            sum[j] = sum[j-1];
            add(sum[j], dp[i][j]);
        }
        for(int j=0; j<M; j++){
            int64_t result = (sum[R[j]] - sum[L[j]-1] + MOD) % MOD;
            add(dp[i+1][L[j]], result);
            add(dp[i+1][R[j]+1], MOD - result);
        }
        for(int j=1; j<=N; j++) add(dp[i+1][j], dp[i+1][j-1]);
    }
    cout << dp[K][N] << endl;
    return 0;
}
0