fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. template<typename T>
  11. void maximize(T& a, const T& b) {
  12. 	if (a < b) a = b;  
  13. }
  14.  
  15. template<typename T>
  16. void minimize(T& a, const T& b) {
  17. 	if (b < a) a = b; 
  18. }
  19.  
  20. const int N = 1e5 + 5; 
  21.  
  22. int n, m; ll P, C; 
  23. int a[N]; 
  24. int s[6]; 
  25.  
  26. int number_of_subtask() {
  27. 	if (n <= 10 && m == 1) return 1; 
  28. 	if (m == 2) return 3; 
  29. 	return 4; 
  30. }
  31.  
  32. ll sqr(int x) {
  33. 	return 1ll * x * x; 
  34. }
  35.  
  36. namespace sub1 {
  37. 	// Tồn tại một hoán vị sao cho việc chọn các cột gỗ từ 1 đến i (với i nào đấy) để thi công cho ra lợi nhuận tối ưu nhất
  38. 	void solve() {
  39. 		sort(a + 1, a + n + 1); 
  40.  
  41. 		ll best = -LINF;  
  42. 		do {
  43. 			int mn = INF, mx = -INF; 
  44. 			ll profit = 0;  
  45. 			for (int i = 1; i <= n; i++) {
  46. 				minimize(mn, a[i]); 
  47. 				maximize(mx, a[i]); 
  48. 				if (i % s[0] == 0) {
  49. 					profit += P - sqr(mx - mn) * C;
  50. 					maximize(best, profit);  
  51. 					mn = INF, mx = -INF; 
  52. 				}
  53. 			}
  54. 		}
  55. 		while (next_permutation(a + 1, a + n + 1)); 
  56.  
  57. 		cout << best << '\n'; 
  58. 	}
  59. }
  60.  
  61. // Subtask 3, 4: 
  62. // Khi sort lại các cột gỗ theo chiều cao a(i) thì ta có nhận xét:
  63. // Khi chọn thi công cho mẫu nhà thứ j thì nên chọn s(j) cột gỗ liên tiếp nhau  
  64.  
  65. ll cost(int i, int j) {
  66. 	return P - sqr(a[j] - a[i]) * C; 
  67. }
  68.  
  69. namespace sub3 {
  70. 	ll dp[N][2][2]; // dp[i][0/1][0/1] = Lợi nhuận lớn nhất đạt được khi xét đến cột gỗ thứ i
  71. 					//					 đã thi công ít nhất 1 ngôi nhà/chưa thi công ngôi nhà nào cho mẫu nhà thứ 1 
  72. 					//					 đã thi công ít nhất 1 ngôi nhà/chưa thi công ngôi nhà nào cho mẫu nhà thứ 2
  73. 	void solve() {
  74. 		sort(a + 1, a + n + 1); 
  75.  
  76. 		for (int i = 0; i <= n; i++) {
  77. 			for (int x = 0; x <= 1; x++) {
  78. 				for (int y = 0; y <= 1; y++) dp[i][x][y] = -LINF; 
  79. 			}
  80. 		}
  81. 		dp[0][0][0] = 0;   
  82.  
  83. 		for (int i = 0; i < n; i++) {
  84. 			for (int x = 0; x <= 1; x++) {
  85. 				for (int y = 0; y <= 1; y++) {
  86. 					if (dp[i][x][y] == -LINF) continue;
  87. 					// không thi công cho mẫu nhà nào
  88. 					maximize(dp[i + 1][x][y], dp[i][x][y]); 
  89.  
  90. 					// thi công cho mẫu nhà thứ 1
  91. 					if (i + s[0] <= n) {
  92. 						maximize(dp[i + s[0]][1][y], dp[i][x][y] + cost(i + 1, i + s[0])); 
  93. 					}
  94.  
  95. 					// thi công cho mẫu nhà thứ 2
  96. 					if (i + s[1] <= n) {
  97. 						maximize(dp[i + s[1]][x][1], dp[i][x][y] + cost(i + 1, i + s[1])); 
  98. 					}
  99. 				}
  100. 			}
  101. 		}
  102.  
  103. 		cout << dp[n][1][1] << '\n'; 
  104. 	}
  105. }
  106.  
  107. namespace sub4 {
  108. 	ll dp[N][1 << 6]; // dp[i][mask] = Lợi nhuận lớn nhất đạt được khi xét đến cột gỗ thứ i 
  109. 					  // với mask là tập hợp các mẫu nhà đã có ít nhất 1 ngôi nhà được thi công
  110. 	void solve() {
  111. 		sort(a + 1, a + n + 1);   
  112.  
  113. 		for (int i = 0; i <= n; i++) {
  114. 			for (int mask = 0; mask < (1 << m); mask++) {
  115. 				dp[i][mask] = -LINF; 
  116. 			}
  117. 		}
  118. 		dp[0][0] = 0;  
  119.  
  120. 		for (int i = 0; i < n; i++) {
  121. 			for (int mask = 0; mask < (1 << m); mask++) {
  122. 				if (dp[i][mask] == -LINF) continue; 
  123. 				// không thi công cho mẫu nhà nào
  124. 				maximize(dp[i + 1][mask], dp[i][mask]); 
  125.  
  126. 				// thi công cho một mẫu nhà thứ j nào đấy
  127. 				for (int j = 0; j < m; j++) {
  128. 					if (i + s[j] <= n) {
  129. 						int new_mask = mask | (1 << j); 
  130. 						maximize(dp[i + s[j]][new_mask], dp[i][mask] + cost(i + 1, i + s[j])); 	
  131. 					}
  132. 				}
  133. 			}
  134. 		}
  135.  
  136. 		cout << dp[n][(1 << m) - 1] << '\n'; 
  137. 	}
  138. }
  139.  
  140. int main() {
  141. 	ios::sync_with_stdio(0); cin.tie(0);  	
  142. 	// freopen("WHOME.INP", "r", stdin); 
  143. 	// freopen("WHOME.OUT", "w", stdout); 
  144. 	cin >> n >> m >> P >> C; 
  145. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  146. 	for (int i = 0; i < m; i++) cin >> s[i]; 
  147.  
  148. 	int subtask = number_of_subtask();  
  149.  
  150. 	if (subtask == 1) sub1::solve(); 
  151. 	if (subtask == 3) sub3::solve(); 
  152. 	if (subtask == 4) sub4::solve(); 
  153. }
Success #stdin #stdout 0.01s 5704KB
comments (?)
stdin
copy 
10 2 11 1
14 5 6 4 4 4 7 8 9 1
4 2
stdout
copy 
30
https://ideone.com/h7JFre
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!