oj.uz

Submission #123386

# Submission time Handle Problem Language Result Execution time Memory
123386 2019-07-01T10:31:27 Z mechfrog88 Journey (NOI18_journey) C++14
100 / 100
 344 ms 12024 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 388 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 388 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 4 ms 528 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 388 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 4 ms 528 KB Output is correct
7 Correct 72 ms 9628 KB Output is correct
8 Correct 44 ms 12024 KB Output is correct
9 Correct 35 ms 3420 KB Output is correct
10 Correct 344 ms 5088 KB Output is correct