Submission #1111449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111449		simuyu	Trains (BOI24_trains)	C++14	21 / 100	2073 ms	3472 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pl pair<long, long>
#define pll pair<ll, ll>
#define f first
#define s second
#define MOD 1000000007

ll ress[100005], ds[100005], xs[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long N;
    cin >> N;

    for (long i=1; i<1+N; i++) {
        cin >> ds[i] >> xs[i];
    }

    ll xp, res;
    for (long idx=N; idx>0; idx--) {
        // if no trains
        if (ds[idx] == 0) {
            ress[idx] = 1;
            continue;
        }

        xp = min(xs[idx], (N-idx)/ds[idx]);

        if (xp == 0) {
            ress[idx] = 1;
            continue;
        }

        res = 1;
        // now loop
        for (long p=1; p<=xp; p++) {
            res += ress[idx+ds[idx]*p];
            res = res%MOD;
        }

        // add to memo
        ress[idx] = res;
    }

    /*cout << "DEBUG: ";
    for (int i=1; i<=N; i++) {
        cout << ress[i] << ' ';
    }
    cout << endl;*/

    cout << ress[1] << '\n';


    return 0;
}

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