Submission #828899

#	Time	Username	Problem	Language	Result	Execution time	Memory
828899		NK_	Journey (NOI18_journey)	C++17	100 / 100	53 ms	6228 KiB

journey

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;

const int INF = 5e8 + 1;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M, H; cin >> N >> M >> H;

	V<vpi> nxt(N);
	for(int i = 0; i < N - 1; i++) {
		for(int t = 0; t < H; t++) {
			int u, x; cin >> u >> x;
			if (u <= i) continue;
			nxt[i].pb(mp(u, x));
		}
	}

	V<vi> dp(N, vi(M, 0));
	dp[0][0] = 1;

	for(int u = 0; u < N; u++) {
		for(auto& e : nxt[u]) {
			auto [v, d] = e;

			int ways = 0;
			for(int x = 0; x + d < M; x++) {
				ways = min(INF, ways + dp[u][x]);
				dp[v][x + d] = min(INF, dp[v][x + d] + ways);
			}
		}
	}

	for(int x = 0; x < M; x++) cout << dp[N-1][x] << " ";
	cout << nl;

	exit(0-0);
}					

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