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