Submission #776218

#	Time	Username	Problem	Language	Result	Execution time	Memory
776218		MasterTaster	Toll (BOI17_toll)	C++14	100 / 100	1743 ms	5036 KiB

toll

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 50010

using namespace std;

int n, m, k, q;
//map<pair<pii, pii>, int> dp;
int w[MAXN][6], ress[MAXN];

/*int resi(int a, int b, int x, int y)
{
	if (dp[{{a, b}, {x, y}}]) return dp[{{a, b}, {x, y}}];
	if ((a+1)==b) return 1000000010;

	int mid=a+(b-a)/2;
	int ress=1000000010;
	for (int i=0; i<k; i++)
	{
		ress=min(ress, resi(a, mid, x, i)+resi(mid, b, i, y));
	}

	dp[{{a, b}, {x, y}}]=ress;
	return ress;
}*/

int main(){
	cin>>k>>n>>m>>q;

	for (int i=0; i<n; i++) for (int j=0; j<k; j++) w[i][j]=1000000010;
	for (int i=0; i<m; i++)
	{
		int u, v, t; cin>>u>>v>>t;
		w[u][v%k]=t;
	}

	while (q--)
	{
		int x, y; cin>>x>>y;

		for (int i=x; i<=y; i++) ress[i]=1000000010;
		ress[x]=0;

		for (int i=x; i<(y/k)*k; i++)
		{
			for (int j=0; j<k; j++)
			{
				ress[((i/k)+1)*k+j]=min(ress[((i/k)+1)*k+j], ress[i]+w[i][j]);
				//cout<<i<<" do "<<((i/k)+1)*k+j<<" kosta "<<ress[((i/k)+1)*k+j]<<endl;
			}
		}

		if (ress[y]>=1000000010) cout<<-1<<"\n";
		else cout<<ress[y]<<"\n";

	}

}

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