제출 #1111447

#제출 시각아이디문제언어결과실행 시간메모리
1111447simuyuTrains (BOI24_trains)C++14
8 / 100
149 ms2688 KiB
#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];
        }

        // 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;
}
#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...