Submission #1109190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109190		Captain_Georgia	Trains (BOI24_trains)	C++17	8 / 100	2076 ms	2260 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;
            if (it[0] > i) {
                int fi = ((i - it[1]) / arr[it[1]][0]);
                if (fi * arr[it[1]][0] + it[1] < i) {
                    continue;
                }
                dp[it[1]] = (dp[it[1]] + dp[i]) % mod;
                if (fi - 1 <= 0) {
                    continue;
                }
                fi --;
                pq.push({fi * arr[it[1]][0] + it[1], it[1]});
            } else {
                int fi = ((it[0] - it[1]) / arr[it[1]][0]);
                if (fi * arr[it[1]][0] + it[1] < i) {
                    continue;
                }
                dp[it[1]] = (dp[it[1]] + dp[i]) % mod;
                if (fi - 1 <= 0) {
                    continue;
                }
                fi --;
                pq.push({fi * arr[it[1]][0] + it[1], 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