fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7.  
  8. using pii = pair<int, int>;
  9. using pll = pair<long long, long long>;
  10.  
  11. #define pb push_back
  12. #define ins insert
  13. #define fi first
  14. #define se second
  15. #define btpc __builtin_popcount
  16. #define btclz __builtin_clz
  17.  
  18. #define sz(x) (int)(x.size());
  19. #define all(x) x.begin(), x.end()
  20. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  21.  
  22. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  23.  
  24. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  25. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  26. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  27.  
  28. template<class X, class Y>
  29.     bool minimize(X &x, const Y &y) {
  30.         if (x > y)
  31.         {
  32.             x = y;
  33.             return true;
  34.         }
  35.         return false;
  36.     }
  37. template<class X, class Y>
  38.     bool maximize(X &x, const Y &y) {
  39.         if (x < y)
  40.         {
  41.             x = y;
  42.             return true;
  43.         }
  44.         return false;
  45.     }
  46.  
  47. const int MOD = 1e9 + 7; //998244353
  48.  
  49. /* Author : Le Ngoc Bao Anh, A5K37 Le Quy Don High School for Gifted Student, Da Nang */
  50.  
  51. /*       University of Wollongong       */
  52.  
  53. const long long INF = 1e18;
  54. const int N = 1e5 + 10;
  55.  
  56. pll calc(ll x, ll y, ll z, ll k, ll p) {
  57. 	ll cycle = (p / k);
  58. 	ll d = 0;
  59. 	ll cost = 0;
  60. 	cost += cycle * k * x + y * cycle;
  61. 	d = cycle * k;
  62. 	p %= k;
  63. 	z -= k * cycle * (cycle + 1) / 2;
  64.  
  65. 	d += p;
  66. 	cost += p * x;
  67.  
  68. 	ll t = 0;
  69. 	if(z > 0) {
  70. 		t = (z + d - 1) / d;
  71. 		cost += y * t;
  72. 	}
  73.  
  74. 	return {cost, t};
  75. }
  76.  
  77. void BaoJiaoPisu() {
  78. 	ll x, y, z, k; cin >> x >> y >> z >> k;
  79.  
  80. 	ll ans = INF;
  81. 	for(int i = 1; i <= 10000; i++) {
  82. 		ans = min(ans, calc(x, y, z, k, i).fi);
  83. 	}
  84.  
  85. 	for(int i = 0; i <= 10000; i++) {
  86. 		ll l = 1, r = z;
  87. 		while(l <= r) {
  88. 			ll mid = (l + r) >> 1;
  89. 			pll cur = calc(x, y, z, k, mid);
  90. 			ans = min(ans, cur.fi);
  91. 			if(cur.se > i) {
  92. 				l = mid + 1;
  93. 			} else {
  94. 				r = mid - 1;
  95. 			}
  96. 		}	
  97. 	}
  98.  
  99. 	cout << ans << '\n';
  100. }
  101.  
  102. int main()
  103. {
  104.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  105.     #ifndef ONLINE_JUDGE
  106.     freopen("input.txt", "r", stdin);
  107.     freopen("output.txt", "w", stdout);
  108.     #else 
  109.     //online
  110.     #endif
  111.  
  112.     int tc = 1, ddd = 0;
  113.     cin >> tc;
  114.     while(tc--) {
  115.         //ddd++;
  116.         //cout << "Case #" << ddd << ": ";
  117.         BaoJiaoPisu();
  118.     }
  119. }
Success #stdin #stdout 0.02s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-9223136246435331424
https://ideone.com/aA3qWy
language:
C++14 (gcc 8.3)
created:
8 hours 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!