제출 #1223847

#제출 시각아이디문제언어결과실행 시간메모리
1223847HanksburgerTrains (BOI24_trains)C++20
100 / 100
121 ms6864 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<pair<int, int>, int> > upd[100005];
int dp[100005], add[105][105], mod=1e9+7;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans=0;
    cin >> n;
    dp[1]=1;
    for (int i=1; i<=n; i++)
    {
        int d, x;
        cin >> d >> x;
        for (auto j:upd[i])
            add[j.first.first][j.first.second]=(add[j.first.first][j.first.second]+j.second)%mod;
        for (int j=1; j<=100; j++)
            dp[i]=(dp[i]+add[j][i%j])%mod;
        if (d && d<=100)
        {
            add[d][i%d]=(add[d][i%d]+dp[i])%mod;
            upd[min(n, i+x*d)+1].push_back({{d, i%d}, mod-dp[i]});
        }
        else if (d>100)
            for (int j=i+d; j<=min(n, i+x*d); j+=d)
                dp[j]=(dp[j]+dp[i])%mod;
        ans=(ans+dp[i])%mod;
    }
    cout << ans;
}
#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...