Submission #538465

#	Time	Username	Problem	Language	Result	Execution time	Memory
538465		blue	Journey (NOI18_journey)	C++17	100 / 100	177 ms	9640 KiB

journey

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

int main()
{
	int n, m, h;
	cin >> n >> m >> h;

	vector<pii> edge[n];

	// cerr << "done\n";

	for(int i = 0; i < n-1; i++)
	{
		for(int e = 0; e < h; e++)
		{
			int j, w;
			cin >> j >> w;
			if(j <= i) continue;
			edge[i].push_back({j, w});
		}

		sort(edge[i].begin(), edge[i].end(), [] (pii x, pii y)
		{
			return x.second < y.second;
		});
	}


	ll dp[m][n];
	for(int d = 0; d < m; d++)
		for(int i = 0; i < n; i++)
			dp[d][i] = 0;

	dp[0][0] = 1;

	ll res[m];

	for(int d = 0; d < m; d++)
	{
		for(int i = 0; i < n; i++)
		{
			// cerr << d << ' ' << i << " : " << dp[d][i] << '\n';

			res[d] = min(5'0000'0001LL, dp[d][i]);

			if(d >= 1)
			{
				dp[d][i] = min(dp[d-1][i] + dp[d][i], 5'0000'0001LL);
			}

			for(pii e : edge[i])
			{
				if(d + e.second >= m) break;
				dp[d + e.second][e.first] = min(dp[d + e.second][e.first] + dp[d][i], 5'0000'0001LL);
			}
		}
	}

	// cout << dp[0][n-1] << ' ';
	// for(int d )

	// for(int d = 1; d < m; d++) cout << min(dp[d][n-1] - dp[d-1][n-1], 5'0000'0001LL) << ' ';
	// cout << '\n';

	for(int d = 0; d < m; d++) cout << res[d] << ' ';
		cout << '\n';

}

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31