Submission #1304258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304258		kirakosyan	Trains (BOI24_trains)	C++20	100 / 100	443 ms	317792 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>


using namespace std;
using ll = long long;
ll mod = 1e9 + 7;
ll gcd(ll a, ll b) {
    if (b == 0)return a;
    else return gcd(b, a % b);
}
void solve() {
    ll n; cin >> n;
    vector<ll>d(n), x(n);
    for (ll i = 0; i < n; i++) {
        cin >> d[i] >> x[i];
    }
    ll armat = 400;
    vector<ll>dp(n);
    dp[0] = 1;
    vector<vector<ll>>pref(armat, vector<ll>(n));
    for (ll i = 0; i < n; i++) {
        for (ll j = 1; j < armat; j++) {
            if (i - j >= 0) {
                pref[j][i] += pref[j][i-j];
                if (pref[j][i] >= mod)pref[j][i] -= mod;
            }
            dp[i] += pref[j][i];
            if (dp[i] >= mod)dp[i] -= mod;
        }
        if (d[i] == 0)continue;
        if (d[i] >= armat) {
            for (ll j = i + d[i]; j <= min(n - 1, i + d[i] * x[i]); j += d[i]) {
                dp[j] += dp[i];
                if (dp[j] >= mod)dp[j] -= mod;
            }
        }
        else {
            if (i + d[i] < n) {
                pref[d[i]][i + d[i]] += dp[i];
                if (pref[d[i]][i + d[i]] >= mod)pref[d[i]][i + d[i]] -= mod;
            }
            if (i + d[i] * (x[i]+1) < n) {
                pref[d[i]][i + d[i] * (x[i] + 1)] -= dp[i];
                if (pref[d[i]][i + d[i] * (x[i] + 1)] < 0) pref[d[i]][i + d[i] * (x[i] + 1)] += mod;
            }
        }
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ans += dp[i];
        if (ans >= mod)ans -= mod;
    }
    cout << ans << endl;

}


signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

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