Submission #689876

#	Time	Username	Problem	Language	Result	Execution time	Memory
689876		dsyz	Journey (NOI18_journey)	C++17	100 / 100	42 ms	10832 KiB

journey

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M,H;
	cin>>N>>M>>H;
	pair<ll,ll> flight[N - 1][H];
	for(ll i = 0;i < N - 1;i++){
		for(ll j = 0;j < H;j++){
			cin>>flight[i][j].first>>flight[i][j].second;
		}
	}
	ll dp[N][M];
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(ll i = 0;i < N - 1;i++){
		for(ll days = 1;days < M;days++){
			dp[i][days] += dp[i][days - 1];
		}
		for(ll j = 0;j < H;j++){
			if(flight[i][j].first > i){
				ll a = i;
				ll b = flight[i][j].first;
				ll k = flight[i][j].second;
				for(ll days = 0;days < M - k;days++){
					dp[b][days + k] += dp[i][days];
					dp[b][days + k] = min(dp[b][days + k],500000001ll);
				}
			}
		}
	}
	for(ll j = 0;j < M;j++){
		cout<<min(dp[N - 1][j],500000001ll)<<" ";
	}
	cout<<'\n';
}

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:24:8: warning: unused variable 'a' [-Wunused-variable]
   24 |     ll a = i;
      |        ^

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31