結果
問題 | No.801 エレベーター |
ユーザー |
|
提出日時 | 2019-03-17 23:03:36 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 118 ms / 2,000 ms |
コード長 | 794 bytes |
コンパイル時間 | 1,330 ms |
コンパイル使用メモリ | 159,928 KB |
実行使用メモリ | 74,028 KB |
最終ジャッジ日時 | 2024-07-08 01:46:29 |
合計ジャッジ時間 | 4,080 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define MOD 1000000007int dp[3010][3010];signed main(){int n, m, k;int l[3010], r[3010];cin >> n >> m >> k;for(int i = 0;i < m;i++){cin >> l[i] >> r[i];}dp[0][1] = 1;for(int i = 1;i <= k;i++){int ta[3010] = {};for(int j = 1;j <= n;j++){dp[i-1][j] = (dp[i-1][j] + dp[i-1][j-1]) % MOD;}for(int j = 0;j < m;j++){int tmp = (MOD+dp[i-1][r[j]] - dp[i-1][l[j]-1]) % MOD;ta[r[j]+1] -= tmp;ta[l[j]] += tmp;}int imos = ta[0];for(int j = 1;j <= n;j++){imos += ta[j];dp[i][j] = imos % MOD;}}cout << dp[k][n] << endl;}