Submission #1155658

#TimeUsernameProblemLanguageResultExecution timeMemory
1155658adiyerTrains (BOI24_trains)C++20
100 / 100
388 ms159320 KiB
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define len(x) (ll) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

const int N = 1e5 + 11;
const int mod = 1e9 + 7;
const int SQ = 200;
const ll inf = 2e18 + 12;

ll n;
ll x[N], d[N], p[N], dp[N], s[N][SQ];

void add(ll &a, ll b){
    a += b, a %= mod, a += mod, a %= mod;
}

signed main(){
    cin >> n, dp[1] = 1;
    for(ll i = 1; i <= n; i++) cin >> d[i] >> x[i];
    for(ll i = 1; i <= n; i++){
        for(ll t = 1; t < SQ; t++) add(dp[i], s[i][t]);
        if(d[i] >= SQ){
            for(ll t = 1; t <= x[i] && i + t * d[i] <= n; t++) add(dp[i + t * d[i]], dp[i]);
        }
        else{
            if(d[i] && x[i]){
                add(s[i][d[i]], dp[i]);
                if(i + (x[i] + 1) * d[i] <= n)
                    add(s[i + (x[i] + 1) * d[i]][d[i]], -dp[i]);
            }
        }
        for(ll t = 1; t < SQ && i + t <= n; t++) add(s[i + t][t], s[i][t]);
    }
    for(ll i = 2; i <= n; i++) add(dp[1], dp[i]);
    cout << dp[1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...