結果

問題 No.801 エレベーター
ユーザー betrue12
提出日時 2019-03-17 21:58:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 245 ms / 2,000 ms
コード長 804 bytes
コンパイル時間 2,118 ms
コンパイル使用メモリ 194,368 KB
最終ジャッジ日時 2025-01-06 22:59:52
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
a = (a+b) % MOD;
}
int main(){
int N, M, K, L[3000], R[3000];
cin >> N >> M >> K;
for(int i=0; i<M; i++){
cin >> L[i] >> R[i];
}
static int64_t dp[3001][3002];
dp[0][1] = 1;
for(int i=0; i<K; i++){
int64_t sum[3001] = {0};
for(int j=1; j<=N; j++){
sum[j] = sum[j-1];
add(sum[j], dp[i][j]);
}
for(int j=0; j<M; j++){
int64_t result = (sum[R[j]] - sum[L[j]-1] + MOD) % MOD;
add(dp[i+1][L[j]], result);
add(dp[i+1][R[j]+1], MOD - result);
}
for(int j=1; j<=N; j++) add(dp[i+1][j], dp[i+1][j-1]);
}
cout << dp[K][N] << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0