oj.uz

Submission #538464

# Submission time Handle Problem Language Result Execution time Memory
538464 2022-03-17T02:15:39 Z blue Journey (NOI18_journey) C++17
43 / 100
 2 ms 408 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;

	for(int d = 0; d < m; d++)
	{
		for(int i = 0; i < n; i++)
		{
			if(d >= 1)
			{
				dp[d][i] = dp[d-1][i] + dp[d][i];
			}

			for(pii e : edge[i])
			{
				if(d + e.second >= m) break;
				dp[d + e.second][e.first] = dp[d + e.second][e.first] + dp[d][i];
			}
		}
	}

	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';

}

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 300 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
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 2 ms 408 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 2 ms 408 KB Output isn't correct
6 Halted 0 ms 0 KB -