Submission #1223842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223842		Hanksburger	Trains (BOI24_trains)	C++20	0 / 100	6 ms	2884 KiB

Main

#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[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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29