結果
問題 | No.801 エレベーター |
ユーザー |
![]() |
提出日時 | 2019-03-17 23:05:47 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 449 ms / 2,000 ms |
コード長 | 956 bytes |
コンパイル時間 | 617 ms |
コンパイル使用メモリ | 84,876 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-08 01:51:52 |
合計ジャッジ時間 | 8,301 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <set>#include <queue>#include <string>#include <iomanip>#include <algorithm>#include <cmath>#include <stdio.h>using namespace std;#define int long longint MOD = 1000000007;signed main() {cin.tie(0);ios::sync_with_stdio(false);int N, M, K;cin >> N >> M >> K;vector<int> L(M);vector<int> R(M);for (int i = 0; i < M; i++) {cin >> L[i] >> R[i];}vector<int> dp(N + 2, 0);dp[1] = 1;for (int i = 0; i < K; i++) {for (int j = 1; j <= N + 1; j++) {dp[j] = (dp[j] + dp[j - 1]) % MOD;}vector<int> ndp(N + 2, 0);for (int j = 0; j < M; j++) {int sum = dp[R[j]] - dp[L[j] - 1];if (sum < 0)sum += MOD;ndp[L[j]] = (ndp[L[j]] + sum) % MOD;ndp[R[j] + 1] -= sum;if (ndp[R[j] + 1] < 0)ndp[R[j] + 1] += MOD;}for (int j = 1; j <= N + 1; j++) {ndp[j] = (ndp[j] + ndp[j - 1]) % MOD;}swap(dp, ndp);}cout << dp[N] << endl;}