oj.uz

Submission #674880

# Submission time Handle Problem Language Result Execution time Memory
674880 2022-12-26T12:40:49 Z QwertyPi Journey (NOI18_journey) C++14
100 / 100
 162 ms 17628 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 10011, MAXM = 401;
int dp[MAXN][MAXM];

inline int sat_add(int x, int y){
	return min(500000001, x + y);
}
int main(){
	int n, m, h; cin >> n >> m >> h;
	dp[0][0] = 1;
	for(int i = 0; i < n - 1; i++){
		for(int k = 0; k < MAXM - 1; k++){
			dp[i][k + 1] = sat_add(dp[i][k + 1], dp[i][k]);
		}
		for(int j = 0; j < h; j++){
			int v, t; cin >> v >> t;
			if(v <= i) continue;
			for(int k = 0; k + t < MAXM; k++){
				dp[v][k + t] = sat_add(dp[v][k + t], dp[i][k]);
			}
		}
	}
	for(int i = 0; i < m; i++){
		cout << dp[n - 1][i] << ' ';
	}
	cout << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 452 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 162 ms 17628 KB Output is correct
8 Correct 94 ms 10828 KB Output is correct
9 Correct 12 ms 1696 KB Output is correct
10 Correct 53 ms 2084 KB Output is correct