oj.uz

Submission #141113

# Submission time Handle Problem Language Result Execution time Memory
141113 2019-08-06T18:49:54 Z tincamatei Journey (NOI18_journey) C++14
100 / 100
 145 ms 11128 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 10000;
const int MAX_M = 400;
const int INF = 500000001;
vector<pair<int, int> > graph[MAX_N];

int dp[MAX_M][MAX_N];
int sp[MAX_M][MAX_N];

int main() {
	int n, m, h;
	
	scanf("%d%d%d", &n, &m, &h);

	for(int i = 0; i < n - 1; ++i) {
		for(int j = 0; j < h; ++j) {
			int to, sl;

			scanf("%d%d", &to, &sl);
			if(i < to)
				graph[to].push_back({i, sl});
		}
	}

	for(int i = 0; i < m; ++i)
		sp[i][0] = 1;
	dp[0][0] = 1;
	for(int i = 0; i < m; ++i)
		for(int j = 1; j < n; ++j) {
			for(auto it: graph[j])
				if(it.second <= i)
					dp[i][j] = min(INF, dp[i][j] + sp[i - it.second][it.first]);
			
			if(i > 0)
				sp[i][j] = sp[i - 1][j];
			sp[i][j] = min(INF, sp[i][j] + dp[i][j]);
		}
	
	for(int i = 0; i < m; ++i)
		printf("%d ", dp[i][n - 1]);
	return 0;
}

Compilation message

journey.cpp: In function 'int main()':
journey.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
journey.cpp:22:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &to, &sl);
    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 632 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 4 ms 1404 KB Output is correct
6 Correct 4 ms 1528 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 4 ms 1404 KB Output is correct
6 Correct 4 ms 1528 KB Output is correct
7 Correct 82 ms 6008 KB Output is correct
8 Correct 115 ms 11128 KB Output is correct
9 Correct 52 ms 6648 KB Output is correct
10 Correct 145 ms 8156 KB Output is correct