| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1369518 | Charizard2021 | Trains (BOI24_trains) | C++20 | 147 ms | 163240 KiB |
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long B = 200;
int main(){
long long n;
cin >> n;
vector<long long> d(1 + n);
vector<long long> x(1 + n);
bool sub4 = true;
bool sub3 = true;
for(long long i = 1; i <= n; i++){
cin >> d[i] >> x[i];
if(x[i] < n){
sub4 = false;
}
if(d[i] != 1){
sub3 = false;
}
}
vector<long long> dp(1 + n, 1);
vector<vector<long long> > sum(1 + n, vector<long long>(B));
for(long long i = n; i >= 1; i--){
if(d[i] != 0){
if(d[i] >= B){
long long cur = i;
long long 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;
long long val = min(n + 1, i + x[i] * d[i] + d[i]);
if(val != n + 1){
dp[i] = (dp[i] - sum[val][d[i]]) % MOD;
if(dp[i] < 0) dp[i] += MOD;
}
}
}
}
for(long long 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";
}| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
