fork download 
  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. const int N = 1e2 + 5; 
  12. const int K = 1e2 + 5; 
  13. const int D = 1e2 + 5; 
  14.  
  15. template<typename T>
  16. void maximize(T& a, const T& b) {
  17. 	if (a < b) a = b; 
  18. }
  19.  
  20. int n, k, d;  
  21. int a[N];
  22. ll dp[N][K][D]; // dp[i][j][sum_mod] = Tổng lớn nhất 
  23. 				// khi xét đến phần tử thứ i, đã chọn j phần tử, tổng mod d = sum_mod
  24.  
  25. int main() {
  26. 	ios::sync_with_stdio(false); 
  27. 	cin.tie(nullptr);  	
  28. 	cin >> n >> k >> d; 
  29. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  30.  
  31. 	for (int i = 0; i <= n; i++) {
  32. 		for (int j = 0; j <= k; j++) {
  33. 			for (int sum_mod = 0; sum_mod < d; sum_mod++) {
  34. 				dp[i][j][sum_mod] = -LINF; 
  35. 			}
  36. 		}
  37. 	}
  38. 	dp[0][0][0] = 0; 
  39.  
  40. 	for (int i = 1; i <= n; i++) {
  41. 		for (int j = 0; j <= k; j++) {
  42. 			for (int pre_sum_mod = 0; pre_sum_mod < d; pre_sum_mod++) {
  43. 				// Bỏ qua a[i] 
  44. 				maximize(dp[i][j][pre_sum_mod], dp[i - 1][j][pre_sum_mod]); 
  45. 				// Chọn a[i]
  46. 				if (j > 0) maximize(dp[i][j][(pre_sum_mod + a[i]) % d], dp[i - 1][j - 1][pre_sum_mod] + a[i]); 
  47. 			}
  48. 		}
  49. 	}
  50.  
  51. 	ll ans = dp[n][k][0]; 
  52. 	if (ans < 0) ans = -1;  
  53. 	cout << ans << '\n'; 
  54. }
  55.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
4 2 2
1 2 3 4
stdout 
6
https://ideone.com/Eg7Vj3
language:
C++14 (gcc 8.3)
created:
39 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!