Submission #865423

#	Time	Username	Problem	Language	Result	Execution time	Memory
865423		Trisanu_Das	Journey (NOI18_journey)	C++17	100 / 100	87 ms	16248 KiB

journey

#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 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31