Submission #924550

#	Time	Username	Problem	Language	Result	Execution time	Memory
924550		Ghulam_Junaid	Toll (BOI17_toll)	C++17	100 / 100	310 ms	57444 KiB

toll

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

const int N = 5e4 + 10;
const int T = 270;
const int inf = 1e9 + 7;

int k, n, m, q, dp[N][T];
vector<pair<int, int>> g[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> k >> n >> m >> q;

    for (int i = 0; i < m; i ++){
        int a, b, t;
        cin >> a >> b >> t;
        g[a].push_back({t, b});
    }

    for (int i = n - 1; i >= 0; i --){
        for (int j = 0; j < T; j ++)
            dp[i][j] = inf;

        dp[i][0] = 0;
        for (auto [w, u] : g[i]){
            int d = u - i;
            dp[i][d] = w;
            for (int j = 1; j < T; j ++){
                int ud = (i + j) - u;
                if (ud < 0) continue;

                dp[i][j] = min(dp[i][j], w + dp[u][ud]);
            }
        }
    }

    for (int i = 0; i < q; i ++){
        int a, b;
        cin >> a >> b;

        assert(a < b);

        int d = b - a;
        
        vector<pair<int, int>> vec;
        vec.push_back({0, a});

        int cur = a;
        while (d >= T){
            vector<pair<int, int>> nxt;
            for (int j = 9; j > 0; j --){
                int v = cur + T - j;
                int best = inf;
                for (auto [dist, u] : vec)
                    best = min(best, dist + dp[u][v - u]);
                
                if (best == inf) continue;
                nxt.push_back({best, v});
            }

            vec = nxt;

            int dist = T - 9;
            if (nxt.size())
                dist = nxt[0].second - cur;
            cur += dist;
            d -= dist;
        }

        int ans = inf;
        for (auto [dist, v] : vec){
            int d = b - v;
            if (d < 0 or d >= T) continue;
            ans = min(ans, dist + dp[v][d]);
        }

        if (ans >= inf)
            ans = -1;

        cout << ans << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44