fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. #define int long long
  5.  
  6. using namespace std;
  7. const int MAXN = (1 << 20);
  8. const int inf = (int)1e17 + 42;
  9.  
  10. int n, l, t;
  11. int a[MAXN], x[MAXN];
  12.  
  13. void read()
  14. {
  15. 	cin >> n >> l >> t;
  16. 	for(int i = 0; i < n; i++)
  17. 		cin >> x[i] >> a[i];
  18. }
  19.  
  20. int dp[MAXN];
  21.  
  22. void solve()
  23. {
  24. 	for(int i = 0; i < n; i++)
  25. 		x[i] *= 2;
  26.  
  27. 	for(int i = 0; i <= 2 * l; i++) dp[i] = inf;
  28. 	dp[0] = 0;
  29.  
  30. 	for(int i = 0; i < n; i++)
  31. 	{
  32. 		multiset<int> st;
  33. 		for(int j = x[i] - t; j < x[i]; j++)
  34. 			if(j >= 0) st.insert(dp[j] + (x[i] - j) * a[i]);
  35. 			else st.insert(x[i] * a[i]);
  36.  
  37. 		for(int j = x[i]; j < min(2 * l + 1, x[i] + t); j++)
  38. 		{
  39. 			dp[j] = min(dp[j], *st.begin() + (j - x[i]) * a[i]);
  40.  
  41. 			if(x[i] - t + j - x[i] >= 0)
  42. 			{
  43. 				auto it = st.find(dp[j - t] + (t - (j - x[i])) * a[i]);
  44. 				if(it != st.end()) st.erase(it);
  45. 			}
  46. 			else st.erase(x[i] * a[i]);
  47.  
  48. 			//cout << i << " -> " << dp[j] << " , " << j << ", " << *st.begin() << endl; 
  49. 		}
  50. 	}
  51.  
  52. 	//for(int i = 0; i <= 2 * l; i++)
  53. 	//	cout << i << ": " << setw(3) << i / 2.0 << " -> " << dp[i] << endl;
  54.  
  55. 	if(dp[l * 2] >= inf) cout << "NEPAVYKS" << endl;
  56. 	else cout << dp[l * 2] << endl;
  57. }
  58.  
  59. #undef int
  60. int main()
  61. {
  62. 	ios_base::sync_with_stdio(false);
  63. 	cin.tie(NULL);
  64.  
  65. 	read();
  66. 	solve();
  67. 	return 0;
  68. }
  69.  
  70.  
Success #stdin #stdout 0s 27992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sMVuhG
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!