Submission #1329634

#TimeUsernameProblemLanguageResultExecution timeMemory
1329634ErJTrains (BOI24_trains)C++20
100 / 100
104 ms7892 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define vvp vector<vp>
#define inf 1000000000
#define mod 1000000007

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;
    vp A(n);
    for(int i = 0; i < n; i++){
        cin >> A[i].first >> A[i].second;
    }
    ll k = 200;
    ll ANS = 0;
    vi ans(n, 0);
    ans[0] = 1;

    //vvi B(k, vi(n, 0));
    //vvi trash(k, vi(n, 0));
    vvp discard(n + 2);

    vector<vi> B(k);
    for(int i = 1; i < k; i++){
        B[i].resize(i + 1, 0);
    }

    for(int i = 0; i < n; i++){
        ll real = ans[i];

        for(int j = 1; j < B.size(); j++){
            ll block = i % j;
            real += B[j][block];
            real %= mod;
        }

        ANS += real;
        ANS %= mod;
        if(A[i].first == 0){
            for(pp trash : discard[i]){
                B[trash.first][i % trash.first] -= trash.second;
                B[trash.first][i % trash.first] %= mod;
            }
            continue;
        }

        if(A[i].first >= k){
            for(int j = 1; j <= A[i].second; j++){
                ll pos = i + j * A[i].first;
                if(pos >= n) break;
                ans[pos] += real;
                ans[pos] %= mod;
            }
        }else{
            ll block = i % A[i].first;
            ll where = i / A[i].first;
            ll pos = block * A[i].first + where;
            B[A[i].first][block] += real;
            B[A[i].first][block] %= mod;
            discard[min((ll)discard.size() - 1, i + A[i].first * A[i].second)].push_back({A[i].first, real});
        }
        for(pp trash : discard[i]){
            B[trash.first][i % trash.first] -= trash.second;
            B[trash.first][i % trash.first] %= mod;
        }

    }
    ANS %= mod;
    ANS += mod;
    ANS %= mod;
    cout << ANS << '\n';

}
#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...