Submission #1311697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311697		samarthkulkarni	Journey (NOI18_journey)	C++20	100 / 100	1336 ms	25848 KiB

journey

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<int, int>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

const int N = 1e4+10;
const ll mx = 5e8+1;

vector<pr> nxt[N];

ll dp[N][410];


void solution() {
	ll n, m, h;
	cin >> n >> m >> h;

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

	dp[0][0] = 1;

	for (int i = 0; i < n-1; i++) {

		for (int j = 0; j < m; j++) {
			if (dp[i][j] == 0 || dp[i][j] == mx) continue;

			for (auto [b, w] : nxt[i]) {

				for (int k = 0; k < m; k++) {

					if (j + w + k > m-1) break;

					dp[b][j+w+k] += dp[i][j];

					dp[b][j+w+k] = min(dp[b][j+w+k], mx);

				}
			}
		}
	}


	for (int i = 0; i < m; i++) {
		cout << dp[n-1][i] << " ";
	}
	cout << endl;

}

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