fork download 
  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. const int N = 1e2 + 5; 
  11. const int K = 1e2 + 5; 
  12. const int D = 1e2 + 5; 
  13.  
  14. template<typename T>
  15. bool maximize(T& a, const T& b) {
  16. 	if (b < a) return false; 
  17. 	a = b; 
  18. 	return true; 
  19. }
  20.  
  21. int n, k, d;  
  22. int a[N];
  23. long long dp[N][K][D]; // dp[i][j][sum_mod] = tổng lớn nhất 
  24. 				 //	khi xét đến phần tử thứ i, đã chọn j thằng, tổng mod d = sum_mod
  25.  
  26. // dp[n][k][0] = tổng lớn nhất thoả mãn điều kiện 
  27.  
  28. int main() {
  29. 	ios::sync_with_stdio(0); cin.tie(0);  	
  30. 	cin >> n >> k >> d; 
  31. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  32.  
  33. 	for (int i = 0; i <= n; i++) {
  34. 		for (int j = 0; j <= k; j++) {
  35. 			for (int sum_mod = 0; sum_mod < d; sum_mod++) {
  36. 				dp[i][j][sum_mod] = -LINF; 
  37. 			}
  38. 		}
  39. 	}
  40.  
  41. 	dp[0][0][0] = 0; 
  42.  
  43. 	for (int i = 0; i < n; i++) {
  44. 		for (int j = 0; j <= k; j++) {
  45. 			for (int sum_mod = 0; sum_mod < d; sum_mod++) {
  46. 				if (dp[i][j][sum_mod] == -LINF) continue;  
  47. 				// xét thằng i + 1
  48. 				// không chọn 
  49. 				maximize(dp[i + 1][j][sum_mod], dp[i][j][sum_mod]); 
  50. 				// chọn 
  51. 				maximize(dp[i + 1][j + 1][(sum_mod + a[i + 1]) % d], dp[i][j][sum_mod] + a[i + 1]); 
  52. 			}
  53. 		}
  54. 	}
  55.  
  56. 	long long ans = dp[n][k][0]; 
  57. 	if (ans == -LINF) ans = -1;  
  58. 	cout << ans << '\n'; 
  59. }
  60.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin 
4 2 2
1 2 3 4
stdout 
6
https://ideone.com/0oKOtg
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!