Submission #631024

#	Time	Username	Problem	Language	Result	Execution time	Memory
631024		Iwanttobreakfree	Toll (BOI17_toll)	C++17	100 / 100	225 ms	36300 KiB

toll

#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int max_n=5e4+3,max_k=5,logn=17,INF=1e18;
int up[max_n][logn][max_k];
int num(int n,int j,int mod,int k){
    int ans=0;
    n-=(n%k);
    n-=k*(1<<j);
    n+=mod;
    return max(ans,n);
}
int kth(int x,int y,int k){
    int ans=INF,dif=x/k-y/k;
    vector<int> sol(k,INF);
    sol[x%k]=0;
    x=x/k*k;
    //cout<<x<<' ';
    if(dif<1)return INF;
    for(int j=logn-1;j>=0;j--){
        if(dif&(1<<j)){
            vector<int> sol2(k,INF);
            for(int to=0;to<k;to++){
                for(int cur=0;cur<k;cur++){
                    sol2[to]=min(sol2[to],sol[cur]+up[x+cur][j][to]);
                }
            }
            x-=k*(1<<j);
            sol=sol2;
        }
    }
    return sol[y%k];
}
signed main(){
    int k,n,m,o,x,y,w;
    cin>>k>>n>>m>>o;
    for(int i=0;i<n;i++)for(int j=0;j<logn;j++)for(int q=0;q<k;q++)up[i][j][q]=INF;
    while(m--){
        cin>>x>>y>>w;
        up[y][0][x%k]=w;
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<logn;j++){
            for(int to=0;to<k;to++){
                for(int mid=0;mid<k;mid++){
                    up[i][j][to]=min(up[i][j-1][mid]+up[num(i,j-1,mid,k)][j-1][to],up[i][j][to]);
                }
            }
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<1;j++){
            for(int to=0;to<k;to++)cout<<up[i][j][to]<<' ';
            cout<<'\n';
        }
    }*/
    while(o--){
        cin>>x>>y;
        int ans=kth(y,x,k);
        if(ans==1e18)cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }
}

Compilation message (stderr)

toll.cpp: In function 'long long int kth(long long int, long long int, long long int)':
toll.cpp:15:9: warning: unused variable 'ans' [-Wunused-variable]
   15 |     int ans=INF,dif=x/k-y/k;
      |         ^~~

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