Submission #1109200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109200		Captain_Georgia	Trains (BOI24_trains)	C++17	8 / 100	2053 ms	1748 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int32_t main () {

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

    int N;
    cin >> N;
    vector<array<int, 2>> arr(N + 1);
    vector<ll> dp(N + 1, 1);
    priority_queue<array<int, 2>> pq;
    for (int i = 1;i <= N;i ++) {
        cin >> arr[i][0] >> arr[i][1];
        if (i + 1LL * arr[i][0] * arr[i][1] <= N) {
            pq.push({i + arr[i][0] * arr[i][1], i});
        } else {
            pq.push({((N - i) / arr[i][0]) * arr[i][0] + i, i});
        }
    }
    for (int i = N;i >= 1;i --) {
        while (pq.size() > 0) {
            auto it = pq.top();
            // cout << i << " " << it[0] << " " << it[1] << "\n";
            // _time ++;
            if (it[0] < i) break;
            pq.pop();
            if (it[1] == i) continue;
            dp[it[1]] = (dp[it[1]] + dp[i]) % mod;
            if (it[0] - arr[it[1]][0] <= it[1]) continue;
            pq.push({it[0] - arr[it[1]][0], it[1]});
        }
    }
    cout << dp[1] << "\n";
}

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