fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. #define int ll
  8. #define rep(i, n) for(int i = 1; (i) <= (n); ++i)
  9. #define forn(i, l, r) for(int i = (l); i <= (r); ++i)
  10. #define ford(i, r, l) for(int i = (r); i >= (l); --i)
  11. #define FOR(i, n) for(int i = 0; i < (n); ++i)
  12. #define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
  13. #define fi first
  14. #define se second
  15. #define pii pair<int, int>
  16. #define pll pair<ll, ll>
  17. #define pb push_back
  18. #define task "LIZIGZAG"
  19. #define endl "\n"
  20. #define sz(a) int(a.size())
  21. #define C(x, y) make_pair(x, y)
  22. #define all(a) (a).begin(), (a).end()
  23. #define bit(i, mask) (mask >> i & 1)
  24.  
  25. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  26. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  27. const int N = 1e5 + 33;
  28. const ll INF = 1e16;
  29. const int LINF = 1e9;
  30. const int LIM = 1e4;
  31. const int MOD = 1e9 + 7;
  32. const int base = 1e5 + 7;
  33.  
  34. int n, m;
  35. int a[N], pre[N];
  36. bool check(int mid)
  37. {
  38. 	int cnt = 0;
  39. 	rep(i, n)
  40. 	{
  41. 		int j = lower_bound(a + 1, a + 1 + n, mid - a[i]) - a;
  42. 		cnt += n - j + 1;
  43. 	}
  44. 	return cnt >= m;
  45. }
  46. void solve()
  47. {
  48. 	cin >> n >> m;
  49. 	rep(i, n) cin >> a[i];
  50. 	sort(a + 1, a + 1 + n);
  51. 	rep(i, n) pre[i] = pre[i - 1] + a[i];
  52.  
  53. 	int l = 0, r = 1e10, ans;
  54. 	while(l <= r)
  55. 	{
  56. 		int mid = l + r >> 1;
  57. 		if(check(mid)) ans = mid, l = mid + 1;
  58. 		else r = mid - 1;
  59. 	}
  60. 	int res =  0;
  61. 	int cnt = 0;
  62. 	rep(i, n)
  63. 	{
  64. 		int j = upper_bound(a + 1, a + 1 + n, ans - a[i]) - a;
  65. 		res += (n - j + 1) * a[i];
  66. 		cnt += (n - j + 1);
  67. 		res += pre[n] - pre[j - 1];
  68. 	}
  69. 	res += (m - cnt) * ans;
  70. 	cout << res << endl;
  71.  
  72. }
  73. signed main()
  74. {
  75.     ios_base::sync_with_stdio(0);
  76.     cin.tie(0); cout.tie(0);
  77.     int TC = 1;
  78. //    if(fopen(task".inp", "r"))
  79. //    {
  80. //        freopen(task".inp", "r", stdin);
  81. //        freopen(task".out", "w", stdout);
  82. //    }
  83.     if(fopen("note.inp", "r"))
  84.     {
  85.         freopen("note.inp", "r", stdin);
  86.         freopen("note.out", "w", stdout);
  87.     }
  88.  
  89.     while(TC--)
  90.     {
  91.         solve();
  92.     }
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5 3
10 14 19 34 33
stdout
copy 
202
https://ideone.com/9cI37L
language:
C++14 (gcc 8.3)
created:
1 day 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!