Submission #519112

#	Time	Username	Problem	Language	Result	Execution time	Memory
519112		Yazan_Alattar	Toll (BOI17_toll)	C++14	100 / 100	165 ms	282180 KiB

toll

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 50007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

ll k, n, m, q, dp[M][6][20][6];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> k >> n >> m >> q;
    for(int i = 0; i <= n / k; ++i) for(int j = 0; j <= k; ++j) for(int bit = 0; bit < 20; ++bit) for(int j2 = 0; j2 <= k; ++j2) dp[i][j][bit][j2] = inf;
    for(int i = 1; i <= m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        dp[a / k][a % k][0][b % k] = c;
    }
    for(int j = 1; j < 20; ++j)
        for(int i = 0; i + (1 << j) <= n / k + 1; ++i)
            for(int from = 0; from < k; ++from)
                for(int to = 0; to < k; ++to)
                    for(int mid = 0; mid < k; ++mid)
                        dp[i][from][j][to] = min(dp[i][from][j][to], dp[i][from][j - 1][mid] + dp[i + (1 << (j - 1))][mid][j - 1][to]);
    while(q--){
        int a, b;
        cin >> a >> b;
        vector <ll> ans;
        for(int i = 0; i < k; ++i) ans.pb(inf);
        int cur = a / k;
        ans[a % k] = 0;
        for(int j = 20; j >= 0; --j){
            if(cur + (1 << j) > b / k) continue;
            vector <ll> nxt;
            for(int i = 0; i < k; ++i) nxt.pb(inf);
            for(int from = 0; from < k; ++from) for(int to = 0; to < k; ++to) nxt[to] = min(nxt[to], ans[from] + dp[cur][from][j][to]);
            cur += (1 << j);
            ans = nxt;
        }
        if(ans[b % k] >= inf) cout << -1 << endl;
        else cout << ans[b % k] << endl;
    }
    return 0;
}

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