Submission #1297220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297220		chaitanyamehta	Journey (NOI18_journey)	C++20	43 / 100	1 ms	572 KiB

journey

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    const long long LIM = 500000001LL; // cap value

    int n, m, h;
    if (!(cin >> n >> m >> h)) return 0;

    // S[destination] = list of pairs (source, stay)
    vector<vector<pair<int,int>>> S(n);
    for (int i = 0; i <= n-2; ++i) {
        for (int r = 0; r < h; ++r) {
            int j, t;
            cin >> j >> t;
            // Only keep flights that go nearer to Brasilia:
            // destination j must be closer => j > i (as statement defines)
            if (j > i && j < n) {
                S[j].emplace_back(i, t);
            }
        }
    }

    if (m == 0) return 0; // nothing to output

    // f[c][d] = number of ways to reach city c in at most d nights (0 <= d < m)
    vector<vector<long long>> f(n, vector<long long>(m, 0LL));

    // base: being at Amman (city 0) counts as 1 way at day 0 (and by recurrence will be 1 for all d)
    f[0][0] = 1;

    // compute for D = 0 separately or inside loop
    for (int C = 1; C < n; ++C) {
        long long cur = 0;
        for (auto &pr : S[C]) {
            int i = pr.first;
            int t = pr.second;
            if (0 - t >= 0) cur += f[i][0 - t]; // only possible if t == 0
        }
        if (cur > LIM) cur = LIM;
        f[C][0] = cur;
    }

    // D >= 1
    for (int D = 1; D < m; ++D) {
        // city 0: no incoming flights; stays 1 way (already there) so f[0][D] = f[0][D-1] (which is 1)
        f[0][D] = f[0][D-1];
        for (int C = 1; C < n; ++C) {
            long long val = f[C][D-1]; // ways that reached C in <= D-1 and wait
            for (auto &pr : S[C]) {
                int i = pr.first;
                int t = pr.second;
                int prevD = D - t;
                if (prevD >= 0) {
                    val += f[i][prevD];
                    if (val >= LIM) { val = LIM; break; }
                }
            }
            if (val > LIM) val = LIM;
            f[C][D] = val;
        }
    }

    // destination is city n-1
    vector<long long> ans(m, 0LL);
    for (int D = 0; D < m; ++D) {
        long long cum = f[n-1][D];
        long long prev = (D == 0 ? 0LL : f[n-1][D-1]);
        long long exact = cum - prev;
        if (exact < 0) exact = 0; // safety (can happen if both capped)
        if (exact > LIM) exact = LIM;
        cout << exact << (D+1 < m ? ' ' : '\n');
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 0 / 26
• Subtask 4: 0 / 31