oj.uz

Submission #1020345

# Submission time Handle Problem Language Result Execution time Memory
1020345 2024-07-12T00:46:24 Z daffuwu Journey (NOI18_journey) C++14
100 / 100
 58 ms 21300 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2464 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2464 KB Output is correct
5 Correct 1 ms 2700 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2464 KB Output is correct
5 Correct 1 ms 2700 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 36 ms 21300 KB Output is correct
8 Correct 38 ms 15184 KB Output is correct
9 Correct 11 ms 4892 KB Output is correct
10 Correct 58 ms 6492 KB Output is correct