oj.uz

Submission #865423

# Submission time Handle Problem Language Result Execution time Memory
865423 2023-10-24T08:10:39 Z Trisanu_Das Journey (NOI18_journey) C++17
100 / 100
 87 ms 16248 KB 
#include<bits/stdc++.h>
using namespace std;

int dp[10005][405], lim = 5e8 + 1;

int main(){
	int n, i, m, c, t, h, j, k; cin >> n >> m >> h;
	dp[0][0] = 1;
	for(i = 0; i < n - 1; i++){
		for(j = 1; j < m; j++) dp[i][j] = min(lim * 1ll, dp[i][j- 1 ] * 1ll + dp[i][j] * 1ll);
		for(j = 0; j < h; j++){
			cin >> c >> t;
			if(c <= i) continue;
			for(k = 0; k + t < m; k++) dp[c][k + t] = min(lim * 1ll,dp[c][k + t] * 1ll + dp[i][k] * 1ll);
		}
	}
	for(i = 0; i < m; i++) cout << dp[n - 1][i] << ' ';
    cout << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 87 ms 16248 KB Output is correct
8 Correct 62 ms 11100 KB Output is correct
9 Correct 12 ms 1624 KB Output is correct
10 Correct 54 ms 2072 KB Output is correct