oj.uz

답안 #538461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538461 2022-03-17T02:11:51 Z blue Journey (NOI18_journey) C++17
0 / 100
 1 ms 212 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;
		});
	}


	int 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] = min(5'0000'0001, dp[d-1][i] + dp[d][i]);
			}

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

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

	for(int d = 1; d < m-1; d++) cout << dp[d][n-1] - dp[d-1][n-1] << ' ';
	cout << '\n';

}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -