Submission #674880

#	Time	Username	Problem	Language	Result	Execution time	Memory
674880		QwertyPi	Journey (NOI18_journey)	C++14	100 / 100	162 ms	17628 KiB

journey

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