oj.uz

Submission #538465

# Submission time Handle Problem Language Result Execution time Memory
538465 2022-03-17T02:23:44 Z blue Journey (NOI18_journey) C++17
100 / 100
 177 ms 9640 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 124 ms 5656 KB Output is correct
8 Correct 144 ms 9640 KB Output is correct
9 Correct 34 ms 3060 KB Output is correct
10 Correct 177 ms 4152 KB Output is correct