fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define up upper_bound
  7. #define vll vector<ll>
  8. #define G vector<vll >
  9. #define gg vector<int>
  10. #define F first
  11. #define S second
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define RFOR(i,a,b) for(int i=a;i>=b;i--)
  15. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  16. #define endl '\n'
  17. #define clr(a) memset(a,0,sizeof(a))
  18. #define all(x) x.begin(),x.end()
  19. #define rll read_ll();
  20. #define gc getchar
  21. #define pc putchar
  22. typedef long long ll;
  23. template<class T> inline T lcm(T a,T b){
  24.         return a/gcd(a,b)*b;
  25. }
  26. template<typename T>
  27. void debug(T first) {
  28.     cout << first << "\n";
  29. }
  30. template<typename T, typename... Args>
  31. void debug(T first, Args... args) {
  32.     cout << first << " ";
  33.     debug(args...);
  34. }
  35.  
  36.  
  37. ll read_ll(){char c=gc();while((c<'0'||c>'9')&&c!='-')c=gc();ll ret=0;int neg=0;if(c=='-')neg=1,c=gc();while(c>='0'&&c<='9'){ret=10*ret+c-48;c=gc();}return neg?-ret:ret;}
  38.  
  39.  
  40. typedef long double ld;
  41. const ld inf = 1e18;
  42.  
  43. struct chtDynamic {  
  44. 	struct line {
  45. 		ll m, b; ld x,s; 
  46. 		ll val; bool isQuery; 
  47. 		line(ll _m = 0, ll _b = 0, ll _s = 0) : 
  48. 			m(_m), b(_b), val(0), x(-inf), s(_s), isQuery(false) {} 
  49.  
  50. 		ll eval(ll x) const { return m * (x-s) + b;	}
  51. 		bool parallel(const line &l) const { return m == l.m; }
  52. 		ld intersect(const line &l) const {
  53. 			return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m);
  54. 		}
  55. 		bool operator < (const line &l) const {
  56. 			if(l.isQuery) return x < l.val;
  57. 			else return m < l.m; 
  58. 		}
  59. 	};
  60.  
  61. 	set<line> hull; 
  62. 	typedef set<line> :: iterator iter; 
  63.  
  64. 	bool cPrev(iter it) { return it != hull.begin(); }
  65. 	bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }
  66.  
  67. 	bool bad(const line &l1, const line &l2, const line &l3) {
  68. 		return l1.intersect(l3) <= l1.intersect(l2); 
  69. 	}
  70. 	bool bad(iter it) {
  71. 		return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
  72. 	}
  73.  
  74. 	iter update(iter it) {
  75. 		if(!cPrev(it)) return it; 
  76. 		ld x = it -> intersect(*prev(it));
  77. 		line tmp(*it); tmp.x = x; tmp.s = it->s;
  78. 		it = hull.erase(it); 
  79. 		return hull.insert(it, tmp);
  80. 	}
  81.  
  82. 	void addLine(ll m, ll b, ld s) { 
  83. 		line l(m, b, s); 
  84. 		iter it = hull.lower_bound(l); 
  85. 		if(it != hull.end() && l.parallel(*it)) {
  86. 			if(it -> b < b) it = hull.erase(it); 
  87. 			else return;
  88. 		}
  89. 		it = hull.insert(it, l); 
  90. 		if(bad(it)) return (void) hull.erase(it);
  91.  
  92. 		while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
  93. 		while(cNext(it) && bad(next(it))) hull.erase(next(it));
  94.  
  95. 		it = update(it);
  96. 		if(cPrev(it)) update(prev(it));
  97. 		if(cNext(it)) update(next(it));
  98. 	}
  99.  
  100. 	ll query(ll x) const { 
  101. 		if(hull.empty()) return -inf;
  102. 		line q; q.val = x, q.isQuery = 1;
  103. 		iter it = --hull.lower_bound(q);
  104. 		return it -> eval(x);
  105. 	}
  106. } ;
  107.  
  108. class Machine {
  109. public:
  110. 	ll Day, Price, Resale, MoneyPerDay;
  111. 	Machine() {
  112.  
  113. 	}
  114.  
  115. };
  116. void solve(ll N, ll C, ll D, int &tc) {
  117. 	chtDynamic ds;
  118. 	vector<Machine> m(N);
  119. 	FOR(i,0,N-1) {
  120. 		cin>>m[i].Day>>m[i].Price>>m[i].Resale>>m[i].MoneyPerDay;
  121. 	}
  122. 	sort(all(m),[](Machine a, Machine b) {
  123. 		return a.Day < b.Day;
  124. 	});
  125. 	ll MaxMoney = C;
  126. 	// if(tc!=47&&tc!=48) 
  127. 	// {
  128. 	for(auto machine : m) {
  129. 		if(machine.MoneyPerDay == 0) continue;
  130. 		MaxMoney = max(MaxMoney, ds.query(machine.Day-1));
  131. 		if(machine.Price > MaxMoney) continue;
  132. 		ll PrevMoney = MaxMoney - machine.Price + machine.Resale;
  133. 		ds.addLine(machine.MoneyPerDay,PrevMoney,(ld)(machine.Day*1.0));
  134. 	}
  135. 	printf("Case %d: %lld\n", tc, max(MaxMoney,ds.query(D)));
  136. 	// }
  137. 	tc++;
  138. }
  139. int main()
  140. {
  141. 	int tc = 1;
  142. 	while(1) {
  143. 		bool ok = true;
  144. 		int N,C,D;
  145. 		cin>>N>>C>>D;
  146. 		if(N==0) break;
  147. 		solve(N,C,D,tc);
  148. 	}
  149. 	return 0;
  150. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
6  10  20
6  12  1  3
1  9  1  2
3  2  1  2
8  20  5  4
4  11  7  4
2 10 9 1
0 0 0
stdout
copy 
Case 1: 44
https://ideone.com/9jrdsI
language:
C++14 (gcc 8.3)
created:
5 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!