제출 #1328083

#제출 시각아이디문제언어결과실행 시간메모리
1328083mattgrytsTrains (BOI24_trains)C++20
100 / 100
749 ms354608 KiB
//The North remembers
//Denysiuk Illia will win EJOI 2026
//Denysiuk Illia will win UJGOI 2026
//Антон Перебейнис ничего не ботал
#include <algorithm>
#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <set>
#include <map>
using namespace std;
const long long INF=1e18+10;
const int mod=1e9+7;
const long long maxlog=22;
const int maxc=11;
using victor = vector<int>;
using victorl = vector<long long>;
using dih = deque<int>;
using pii = pair<int,long long>;
using pll=pair<long long,int>;
const int NIGGA=2*1e5+10;
using ver = pair<long long,pair<int,int>>;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    victorl dp(n,0);
    victor d(n),x(n);
    for(int i=0;i<n;i++)cin>>d[i]>>x[i];
    int sq=0;
    while(1ll*sq*sq<n)sq++;
    vector<vector<victorl>>pref;
    pref.resize(sq+10);
    for(int i=0;i<=sq;i++)pref[i].resize(sq+10);
    for(int i=n-1;i>=0;i--){
        dp[i]=1;
        if(d[i]){
            if(d[i]>=sq){
                for(int t=1;t<=min(x[i],(n-i-1)/d[i]);t++)dp[i]=(dp[i]+dp[i+t*d[i]])%mod;
            }else{
                int sz=pref[d[i]][i%d[i]].size();
                long long pl=0;
                if(sz>0){
                    if(sz<=x[i])pl=pref[d[i]][i%d[i]][sz-1];
                    else pl=(pref[d[i]][i%d[i]][sz-1]-pref[d[i]][i%d[i]][sz-1-x[i]]+mod)%mod;
                }
                dp[i]=(dp[i]+pl)%mod;
            }
        }
        for(int j=1;j<=sq;j++){
            if(pref[j][i%j].empty())pref[j][i%j].push_back(dp[i]);
            else pref[j][i%j].push_back((pref[j][i%j].back()+dp[i])%mod);
        }
    }
    cout<<dp[0];
    return 0;
    
}
#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...