| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1369508 | Charizard2021 | Trains (BOI24_trains) | C++20 | 88 ms | 83624 KiB |
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int B = 200;
int main(){
int n;
cin >> n;
vector<int> d(1 + n);
vector<int> x(1 + n);
for(int i = 1; i <= n; i++){
cin >> d[i] >> x[i];
}
vector<int> dp(1 + n, 1);
int pref = 0;
vector<vector<int> > sum(1 + n, vector<int>(B));
for(int i = n; i >= 1; i--){
if(d[i] != 0){
if(x[i] >= n){
if(d[i] >= B){
int cur = i;
int cnt = 0;
while(cur + d[i] <= n && cnt + 1 <= x[i]){
cur += d[i];
cnt++;
dp[i] = (dp[i] + dp[cur]) % MOD;
}
}
else{
if(i + d[i] <= n){
dp[i] = (dp[i] + sum[i + d[i]][d[i]]) % MOD;
}
}
}
else if(d[i] == 1){
dp[i] = (dp[i] + pref) % MOD;
}
else{
int cur = i;
int cnt = 0;
while(cur + d[i] <= n && cnt + 1 <= x[i]){
cur += d[i];
cnt++;
dp[i] = (dp[i] + dp[cur]) % MOD;
}
}
}
pref = (pref + dp[i]) % MOD;
for(int j = 0; j < B; j++){
if(i + j <= n){
sum[i][j] = sum[i + j][j];
}
sum[i][j] = (sum[i][j] + dp[i]) % MOD;
}
}
cout << dp[1] << "\n";
}| # | 결과 | 실행 시간 | 메모리 | 채점기 출력 |
|---|---|---|---|---|
| 결과를 불러오는 중입니다… | ||||
| # | 결과 | 실행 시간 | 메모리 | 채점기 출력 |
|---|---|---|---|---|
| 결과를 불러오는 중입니다… | ||||
| # | 결과 | 실행 시간 | 메모리 | 채점기 출력 |
|---|---|---|---|---|
| 결과를 불러오는 중입니다… | ||||
| # | 결과 | 실행 시간 | 메모리 | 채점기 출력 |
|---|---|---|---|---|
| 결과를 불러오는 중입니다… | ||||
| # | 결과 | 실행 시간 | 메모리 | 채점기 출력 |
|---|---|---|---|---|
| 결과를 불러오는 중입니다… | ||||
