Submission #1268576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268576		gry3125	Trains (BOI24_trains)	C++20	50 / 100	165 ms	5140 KiB

Main

#include <bits/stdc++.h>
#define ll long long int
#define fi first
#define se second
using namespace std;

ll dp[500][500] = { }, ans[200005] = { };
priority_queue<pair<pair<ll,ll>,pair<ll,ll>>, vector<pair<pair<ll,ll>,pair<ll,ll>>>, greater<pair<pair<ll,ll>,pair<ll,ll>>>> ev;

int main() {
    ll n; cin >> n; ans[1] = 1; ll sum = 0;
    for (ll i = 1; i <= n; i++) {
        ll d, x; cin >> d >> x;
        for (ll j = 1; j*j <= n; j++) {
            ans[i] += dp[i%j][j];
            ans[i] %= 1000000007;
        }
        if (d*d >= x) {
            for (ll j = 1; j <= x && i+j*d <= n; j++) {
            	ans[i+j*d] += ans[i];
            	ans[i+j*d] %= 1000000007;
            }
        } else if (d > 0) {
            dp[i%d][d] += ans[i];
            dp[i%d][d] %= 1000000007;
            ev.push({{i+x*d,ans[i]},{i%d,d}});
        }
        while (!ev.empty() && ev.top().fi.fi <= i) {
            auto cur = ev.top(); ev.pop();
            dp[cur.se.fi][cur.se.se] -= cur.fi.se;
            while (dp[cur.se.fi][cur.se.se] < 0) {
                dp[cur.se.fi][cur.se.se] += 1000000007;
            }
        }
        sum += ans[i]; sum %= 1000000007;
    }
    cout << sum;
    return 0;
}

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