Submission #1020345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020345		daffuwu	Journey (NOI18_journey)	C++14	100 / 100	58 ms	21300 KiB

journey

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

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >
#define mikochi priority_queue<int, vector<int>, greater<int> >

int n, m, h, dp[10003][403], u, v, mx = 500000001, k, ps[1003][403];
vector<pair<int, int> > al[10003];

int main() {
	nyahalo
	int i, j, ii;
	cin >> n >> m >> h;
	for (i=0; i<=n-2; i++) {
		for (j=1; j<=h; j++) {
			cin >> u >> k;
			if (u>i) {
				al[u].push_back(make_pair(i, k));
			}
		}
	}
	for (i=0; i<=m-1; i++) {
		if (i == 0) {
			dp[0][i] = 1;
			ps[0][i] = dp[0][i];
		} else {
			dp[0][i] = 0;
			ps[0][i] = ps[0][i-1]+dp[0][i];
			ps[0][i] = min(ps[0][i], mx);
		}
	}
	for (i=1; i<=n-1; i++) {
		for (j=0; j<=m-1; j++) {
			dp[i][j] = 0;
			for (ii=0; ii<al[i].size(); ii++) {
				u = al[i][ii].first;
				k = al[i][ii].second;
				if (j>=k) {
					dp[i][j] += ps[u][j-k];
					dp[i][j] = min(dp[i][j], mx);
				}
			}
			if (j == 0) {
				ps[i][j] = dp[i][j];
			} else {
				ps[i][j] = ps[i][j-1]+dp[i][j];
				ps[i][j] = min(ps[i][j], mx);
			}
		}
	}
	for (i=0; i<=m-1; i++) {
		cout << dp[n-1][i];
		if (i == m-1) {
			cout << "\n";
		} else {
			cout << " ";
		}
	}
	otsumiko
}

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for (ii=0; ii<al[i].size(); ii++) {
      |               ~~^~~~~~~~~~~~~

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