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.     	int mn = min({cnt[1], rm2, cnt[3]});
  51. 		tmp6 = max(tmp6, i + mn);
  52. 	}
  53. 	ans = max(ans, tmp6);
  54.  
  55. 	// sum == 7 (1, 3, 3) && (2, 2, 3)
  56. 	int tmp7 = 0, mx7 = min(cnt[1], cnt[3] / 2);
  57. 	for (int i = 0; i <= mx7; i++) {
  58. 		int rm3 = cnt[3] - i * 2;
  59. 		tmp7 = max(tmp7, i + min(rm3, cnt[2] / 2));
  60. 	}
  61. 	ans = max(ans, tmp5);
  62.  
  63. 	// sum == 8 (2, 3, 3)
  64. 	ans = max(ans, min(cnt[2], cnt[3] / 2));
  65.  
  66. 	// sum == 9 (3, 3, 3)
  67. 	ans = max(ans, cnt[3] / 3);
  68.  
  69. 	cout << ans << '\n';
  70. }
  71.  
  72. signed main() {
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0); cout.tie(0);
  75.  
  76.     freopen("SANPHAM.inp", "r", stdin);
  77.     freopen("SANPHAM.out", "w", stdout);
  78.  
  79.     cin >> n >> k;
  80.     for (int i = 1; i <= n; i++) {
  81.         cin >> a[i];
  82.         cnt[a[i]]++;
  83.         mx = max(mx, a[i]);
  84.     }
  85.     if (k == 1 && n <= 1000) sub1();
  86.     else if (k == 2) sub2();
  87.     else sub3();
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QugikQ
language:
C++ (gcc 8.3)
created:
3 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!