結果
問題 | No.801 エレベーター |
ユーザー |
![]() |
提出日時 | 2019-03-17 22:35:12 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 675 ms / 2,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 474 ms |
コンパイル使用メモリ | 55,160 KB |
実行使用メモリ | 73,984 KB |
最終ジャッジ日時 | 2024-07-08 00:43:11 |
合計ジャッジ時間 | 12,346 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>using namespace std;typedef long long ll;int N,M,K;int L[3010],R[3010];ll dp[3010][3010] = {},imos[3010] = {},elv[3010] = {},inf = 1e9+7;int main(){cin >> N >> M >> K;for(int i=1;i<=M;i++){cin >> L[i] >> R[i];}dp[0][1] = 1;for(int k=1;k<=K;k++){for(int i=1;i<=N;i++){(dp[k-1][i] += dp[k-1][i-1])%=inf;//累積和}//エレベーター内の移動の総数for(int i=1;i<=N;i++){imos[i] = 0;}for(int i=1;i<=M;i++){elv[i] = (dp[k-1][R[i]]-dp[k-1][L[i]-1]+inf)%inf;(imos[L[i]] += elv[i])%=inf;(imos[R[i]+1] += -elv[i]+inf)%=inf;}for(int i=1;i<=N;i++){(imos[i] += imos[i-1])%=inf;dp[k][i] = imos[i];}}/* for(int i=1;i<=K;i++){for(int j=1;j<=N;j++){cout << dp[i][j] << " ";}cout << endl;}*/ cout << dp[K][N] << endl;}