結果

問題 No.801 エレベーター
コンテスト
ユーザー yuji9511
提出日時 2019-03-18 13:06:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 155 ms / 2,000 ms
コード長 2,171 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,183 ms
コンパイル使用メモリ 161,308 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 07:04:35
合計ジャッジ時間 4,419 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i == n-1];}
#define printp(x,n) for(ll i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18 + 7)
using namespace std;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;
// ll dp[3010][3010] = {};// dp[i][j]: i回の移動の後、j階にいるような乗り方の総数
// ll sum[3010][3010] = {};
// ll sum2[3010][3010] = {};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M,K;
    ll L[3010], R[3010];
    cin >> N >> M >> K;
    rep(i,0,M) cin >> L[i] >> R[i];
    ll dp_cur[3010] = {}, dp_next[3010] = {};
    dp_cur[1] = 1;
    rep(i,0,K){
        memset(dp_next, 0, sizeof(dp_next));
        ll sum[3010] = {};
        rep(i,0,N+1) sum[i+1] = (sum[i] + dp_cur[i]) % MOD;
        rep(i,0,M){
            ll v = (sum[R[i]+1] - sum[L[i]] + MOD) % MOD;
            dp_next[L[i]] += v % MOD;
            dp_next[L[i]] %= MOD;
            dp_next[R[i]+1] += (MOD - v) % MOD;
            dp_next[R[i]+1] %= MOD;
        }
        rep(i,0,N+1){
            dp_next[i+1] += dp_next[i];
            dp_next[i+1] %= MOD;
        }
        rep(i,0,N+1) dp_cur[i] = dp_next[i];
    }
    print(dp_cur[N]);
    // rep(i,0,M){
    //     rep(j,L[i], R[i]+1){
    //         sum[j][L[i]]++;
    //         sum[j][R[i]+1]--;
    //     }
    // }
    // rep(i,0,N+1){
    //     rep(j,0,N+1){
    //         sum[i][j+1] += sum[i][j];
    //     }
    // }

    // rep(i,0,N+1){
    //     rep(j,0,N+1){
    //         sum2[i][j+1] = sum2[i][j] + sum[i][j];
    //     }
    // }

    // dp[0][1] = 1;
    // rep(i,0,K){
    //     rep(j,1,N+1){
    //         dp[i+1][j] += dp[i][k] * 
    //         rep(k,1,N+1){
    //             dp[i+1][j] += dp[i][k] * sum[j][k] % MOD;
    //             dp[i+1][j] %= MOD;
    //         }
    //     }
    // }
    // print(dp[K][N]);
    



 }
0