fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5. const int N = 1e5 + 7;
  6.  
  7. int n, k, mx = 0;
  8. int a[N], cnt[N];
  9.  
  10. void sub1() {
  11. 	int ans = 0;
  12. 	for (int i = 1; i <= n; i++) ans = max(ans, cnt[a[i]]);
  13. 	cout << ans << '\n';
  14. }
  15.  
  16. void sub2() {
  17. 	int ans = 0;
  18. 	for (int i = 2; i <= mx * 2; i++) {
  19. 		int tmp = 0;
  20. 		for (int j = 1; j <= i / 2; j++) {	
  21. 			if (j != i - j) tmp += min(cnt[j], cnt[i - j]);
  22. 			else tmp += cnt[j] / 2;
  23. 		}
  24. 		ans = max(ans, tmp);
  25. 	}
  26. 	cout << ans << '\n';
  27. }
  28.  
  29. void sub3() {
  30. 	int ans = 0;
  31.  
  32. 	// sum == 3 (1, 1, 1)
  33. 	ans = max(ans, cnt[1] / 3);
  34.  
  35. 	// sum == 4 (1, 1, 2)
  36. 	ans = max(ans, min(cnt[1] / 2, cnt[2]));
  37.  
  38. 	// sum == 5 (1, 2, 2) && (1, 1, 3)
  39. 	int tmp5 = 0, mx5 = min(cnt[1] / 2, cnt[3]);
  40. 	for (int i = 0; i <= mx5; i++) {
  41. 		int rm1 = cnt[1] - i * 2;
  42. 		tmp5 = max(tmp5, i + min(rm1, cnt[2] / 2));
  43. 	}
  44. 	ans = max(ans, tmp5);
  45.  
  46. 	// sum == 6 (1, 2, 3) && (2, 2, 2)
  47. 	int tmp6 = 0, mx6 = cnt[2] / 3;
  48. 	for (int i = 0; i <= mx6; i++) {
  49. 		int rm2 = cnt[2] - i * 3;
  50. 		tmp6 = max(tmp6, i + min({cnt[1], rm2, cnt[3]}));
  51. 	}
  52. 	ans = max(ans, tmp6);
  53.  
  54. 	// sum == 7 (1, 3, 3) && (2, 2, 3)
  55. 	int tmp7 = 0, mx7 = min(cnt[1], cnt[3] / 2);
  56. 	for (int i = 0; i <= mx7; i++) {
  57. 		int rm3 = cnt[3] - i * 2;
  58. 		tmp7 = max(tmp7, i + min(rm3, cnt[2] / 2));
  59. 	}
  60. 	ans = max(ans, tmp5);
  61.  
  62. 	// sum == 8 (2, 3, 3)
  63. 	ans = max(ans, min(cnt[2], cnt[3] / 2));
  64.  
  65. 	// sum == 9 (3, 3, 3)
  66. 	ans = max(ans, cnt[3] / 3);
  67.  
  68. 	cout << ans << '\n';
  69. }
  70.  
  71. signed main() {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(0); cout.tie(0);
  74.  
  75.     freopen("SANPHAM.inp", "r", stdin);
  76.     freopen("SANPHAM.out", "w", stdout);
  77.  
  78.     cin >> n >> k;
  79.     for (int i = 1; i <= n; i++) {
  80.         cin >> a[i];
  81.         cnt[a[i]]++;
  82.         mx = max(mx, a[i]);
  83.     }
  84.     if (k == 1 && n <= 1000) sub1();
  85.     else if (k == 2) sub2();
  86.     else sub3();
  87.     return 0;
  88. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i3fJLy
language:
C++ (gcc 8.3)
created:
2 days 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!