Submission #123386

#	Time	Username	Problem	Language	Result	Execution time	Memory
123386		mechfrog88	Journey (NOI18_journey)	C++14	100 / 100	344 ms	12024 KiB

journey

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;	


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,h;
	cin >> n >> m >> h;
	vector <vector <pair<ll,ll>>> arr(n);
	for (int z=0;z<n-1;z++){
		for (int x=0;x<h;x++){
			ll a,b;
			cin >> a >> b;
			arr[z].push_back(make_pair(a,b));
		}
	} 
	vector <vector<ll>> dp(n,vector<ll>(m,0));
	for (int x=0;x<h;x++){
		dp[arr[0][x].first][arr[0][x].second]++;
	}
	ll temp = 0;
	for (int z=1;z<n-1;z++){
		for (int y=0;y<m;y++){
			if (dp[z][y] == 0) continue;
			for (int x=0;x<h;x++){
				if (y+arr[z][x].second >= m) continue;
				if (arr[z][x].first <= z) continue;
				dp[arr[z][x].first][y+arr[z][x].second]+= dp[z][y];
				dp[arr[z][x].first][y+arr[z][x].second] = min(dp[arr[z][x].first][y+arr[z][x].second],ll(500000001));
			}
			if (y < m-1) dp[z][y+1] += dp[z][y];
			dp[z][y] = min(dp[z][y],ll(500000001));
			dp[z][y+1] = min(dp[z][y+1],ll(500000001));
		}
		temp = 0;
	}
	ll c = 0;
	for (int z=0;z<m;z++){
		cout << min(c+dp[n-1][z],ll(500000001)) << " ";
		c += dp[n-1][z];
	} cout << endl;
}

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:34:5: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
  ll temp = 0;
     ^~~~

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