Submission #672895

#	Time	Username	Problem	Language	Result	Execution time	Memory
672895		bogdanvladmihai	Toll (BOI17_toll)	C++14	10 / 100	226 ms	75932 KiB

toll

#include <bits/stdc++.h>
using namespace std;
 
int K, N, M, Q;
 
vector<vector<vector<vector<int>>>> dp;
 
int main() {
    cin >> K >> N >> M >> Q;
 
    dp.resize((N / K + 1), vector<vector<vector<int>>>(ceil(log2(N / K)) + 1, 
                            vector<vector<int>>(K, vector<int>(K, INT_MAX / 2))));
    for (int i = 0; i < M; i++) {
        int a, b, c; cin >> a >> b >> c;
        dp[a / K][0][a % K][b % K] = c;
    }
 
    for (int l = 1; (1 << l) <= (N - 1) / K; l++) {
        for (int g = 0; g <= (N - 1) / K - (1 << l) + 1; g++) {
            for (int m1 = 0; m1 < K; m1++) {
                for (int m2 = 0; m2 < K; m2++) {
                    for (int to = 0; to < K; to++) {
                        dp[g][l][m1][m2] = min(dp[g][l][m1][m2], 
                                            dp[g][l - 1][m1][to] + dp[g + (1 << (l - 1))][l - 1][to][m2]);
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < Q; i++) {
        int a, b; cin >> a >> b;
 
        vector<int> answer(K, INT_MAX / 2);
        answer[a % K] = 0;
 
        int len = b / K - a / K, lst = a / K;
        for (int l = 0; (1 << l) <= len; l++) {
            if ((len & (1 << l)) != 0) {
                vector<int> tmp(K, INT_MAX / 2);
                for (int m = 0; m < K; m++) {
                    for (int from = 0; from < K; from++) {
                        tmp[m] = min(tmp[m], dp[lst][l][from][m] + answer[from]);
                    }
                }
 
                answer = tmp;
                lst |= (1 << l);
            }
        }
 
        if (answer[b % K] >= INT_MAX / 2) {
            cout << "-1\n";
        } else {
            cout << answer[b % K] << "\n";
        }
    }
 
    return 0;
}

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