Submission #1130811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130811		aaa2312	Toll (BOI17_toll)	C++20	100 / 100	364 ms	51704 KiB

toll

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
const ll mod2 = 998244353;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans *= a;
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll pow(ll a, ll b, ll c) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % c;
        b >>= 1;
        a = (a * a) % c;
    }
    return ans;
}

void check(bool b) {
    if (b)
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll k,n,m,q;
    cin>>k>>n>>m>>q;
    ll l=log2(n/k+1)+1;
    vector<vector<vector<ll>>>anc(n,vector<vector<ll>>(l,vector<ll>(k,1e14)));
    while (m--){
        ll a,b,t;
        cin>>a>>b>>t;
        anc[b][0][a%k]=min(anc[b][0][a%k],t);
    }
    for (int i = 1; i < l; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int kk = 0; kk < k; ++kk) {
                for (int ll = 0; ll < k; ++ll) {
                    anc[j][i][ll]=min(anc[j][i][ll], anc[j][i - 1][kk] + anc[max(0LL,(j/k-(1<<(i-1)))*k+kk)][i - 1][ll]);
                }
            }
        }
    }
    while (q--){
        ll a,b;
        cin>>a>>b;
        if (a/k==b/k){
            cout<<-1<<'\n';
            continue;
        }
        ll le=b/k-a/k;
        vector<ll>dist(k,1e14);
        dist[b%k]=0;
        ll cul=b/k;
        for (int i = l-1; i >= 0; --i) {
            if (le&(1<<i)){
                vector<ll>dist2(k,1e14);
                for (int j = 0; j < k; ++j) {
                    for (int ll = 0; ll < k; ++ll) {
                        if (cul*k+j<n)
                        dist2[ll]=min(dist2[ll], dist[j] + anc[cul * k + j][i][ll]);
                    }
                }
                cul-=1<<i;
                swap(dist,dist2);
            }
        }
        if (dist[a%k]==(ll)1e14){
            cout<<-1<<'\n';
        } else{
            cout<<dist[a%k]<<'\n';
        }
    }
    return 0;
}

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