Submission #1111531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111531		simuyu	Trains (BOI24_trains)	C++14	16 / 100	14 ms	4172 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned 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];
ull apsum[100005];
ll num_in_apsum = 0;

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

    apsum[0] = 0;

    ll N;
    cin >> N;

    for (ll i=1; i<1+N; i++) {
        cin >> ds[i] >> xs[i];
        //apsums.push_back(vector<ull>());
        //apsums[apsums.size()-1].push_back(0);
    }

    ull xp, res;
    for (ll idx=N; idx>0; idx--) {
        //cout << "PROCESSING " << idx << endl;

        // if no trains
        if (ds[idx] == 0) {
            res = 1;
            ress[idx] = 1;
        } else {

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

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

                /*
                res = 1;

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

                //cout << "CHECKED IFS" << endl;

                // apsums is from the back. if we need 2, length is 5, then we take apsums[idx][4] - apsums[idx][2]
                //cout << "XP: " << xp << ", SIZE: " << num_in_apsum << endl;
                //cout << apsum[num_in_apsum] << ' ' << apsum[num_in_apsum-xp] << endl;
                res = 1+(apsum[num_in_apsum] + MOD - apsum[num_in_apsum-xp])%MOD;

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

            }

        }

        //cout << "GOT RES: " << res << endl;

        /*cout << "APSUMS: " << endl;
        for (int i=0; i<apsums.size(); i++) {
            cout << ds[i+1] << ": ";
            for (int j=0; j<apsums[i].size(); j++) {
                cout << apsums[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl;*/

        /*cout << "APSUM: ";
        for (int i=0; i<=num_in_apsum; i++) {
            cout << apsum[i] << ' ';
        }
        cout << endl;*/


        //cout << "LEN APSUMS: " << apsums.size() << endl;

        // add to apsums
        // index from back ig = N-idx, if it's % isajfe = 0 then add
        apsum[num_in_apsum+1] = (apsum[num_in_apsum] + res)%MOD;
        num_in_apsum++;
        /*for (int i=0; i<N; i++) {
            if (ds[i+1] == 0) continue;
            //cout << "NEXT START" << endl;
            //cout << N-idx-i << ' ' << (N-idx)%ds[i+1] << endl;
            // it should be -( (N-idx)-(N-i) ) to get distance from idx to i --> basically idx-i
            if (((idx-i-1)%ds[i+1]) == 0) {
                //cout << apsums[i].size() << ", VAL: " << (apsums[i][apsums[i].size()-1]+res)%MOD << endl;
                // add to the apsums
                apsums[i].push_back((apsums[i][apsums[i].size()-1] + res)%MOD);
                //cout << "YES " << i << " WHEN MAX " << N  << endl;
            }
            //cout << "OKAY END" << endl;
        }*/

        //cout << "ADDED TO APSUMS" << endl;

    }

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

    cout << "APSUMS: " << endl;
    for (int i=0; i<apsums.size(); i++) {
        cout << ds[i+1] << ": ";
        for (int j=0; j<apsums[i].size(); j++) {
            cout << apsums[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;*/

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


    return 0;
}

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