結果
問題 | No.801 エレベーター |
ユーザー |
![]() |
提出日時 | 2022-05-27 15:21:50 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 1,093 bytes |
コンパイル時間 | 933 ms |
コンパイル使用メモリ | 141,164 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 15:15:11 |
合計ジャッジ時間 | 3,825 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;const ll MOD = 1000000007;const int MAX_N = 3010;ll dp[MAX_N];ll RUI[MAX_N];ll D[MAX_N];int L[MAX_N];int R[MAX_N];int main() {int N, M, K;cin >> N >> M >> K;for (int i = 0; i < M; ++i) {cin >> L[i] >> R[i];}memset(dp, 0, sizeof(dp));dp[1] = 1;for (int i = 0; i < K; ++i) {memset(RUI, 0, sizeof(RUI));for (int j = 1; j <= N; ++j) {RUI[j] = dp[j] + RUI[j - 1];RUI[j] %= MOD;}memset(D, 0, sizeof(D));for (int j = 0; j < M; ++j) {int l = L[j];int r = R[j];ll sum = (RUI[r] - RUI[l - 1]) % MOD;D[l] += sum;D[l] %= MOD;D[r + 1] -= sum;D[r + 1] %= MOD;}ll sum = 0;for (int j = 1; j <= N; ++j) {sum += (D[j] + MOD);sum %= MOD;dp[j] = sum;}}cout << dp[N] << endl;return 0;}