fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/rope>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. //#pragma GCC optimize("Ofast")
  6. //#pragma GCC optimize("unroll-loops")
  7. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  8. #define ll long long
  9. #define pb push_back
  10. #define x first
  11. #define ld long double
  12. #define y second
  13. #define mk(a,b) make_pair(a,b)
  14. #define rr return 0
  15. #define uid uniform_int_distribution
  16. #define urd uniform_real_distribution
  17. #define sqr(a) ((a)*(a))
  18. #define all(a) a.begin(),a.end()
  19.  
  20. using namespace std;
  21.  
  22. //using namespace __gnu_cxx;
  23. //using namespace __gnu_pbds;
  24. //template<class value, class cmp = less<value> >
  25. //using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  26. //template<class key, class value, class cmp = less<key> >
  27. //using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  28. //
  29. ///// find_by_order()
  30. ///// order_of_key()
  31. //
  32. //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  33. //inline int randll(int l = LONG_MIN, int r = LONG_MAX) {
  34. //    return uid<int>(l, r)(rng);
  35. //}
  36.  
  37. const int N = 1e5 + 11;
  38. ll a[N];
  39. inline ll solve(ll n, ll m) {
  40.     ll pos = n - 2;
  41.     ll ans = 0;
  42.     while (pos > 0 && a[pos] == a[n - 1])
  43.         --pos;
  44.     while (m && a[n - 1]) {
  45. //        cout << a[n - 1] << ' ' << pos << "\n---\n";
  46.         if ((n - 1 - pos) * (a[n - 1] - a[pos]) < m) {
  47.             m -= (n - 1 - pos) * (a[n - 1] - a[pos]);
  48.             a[n - 1] = a[pos];
  49.         }
  50.         else {
  51.             for (int i = n - 2; i > pos; i--)
  52.                 a[i] = a[n - 1];
  53.             ll k = m / (n - 1 - pos);
  54.             ll ost = m - k * (n - 1 - pos);
  55.             for (int i = n - 1; i > pos; i--) {
  56.                 a[i] -= k;
  57.                 a[i] -= (ost > 0);
  58.                 --ost;
  59.             }
  60.             m = 0;
  61.         }
  62.         while (pos > 0 && a[pos] == a[n - 1])
  63.             --pos;
  64.     }
  65.     for (int i = 0; i < n; i++) {
  66.         ans += a[i] * a[i];
  67.     }
  68.     return ans;
  69. }
  70. main()
  71. {
  72.     ios::sync_with_stdio(0);
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0);
  75.     cout.tie(0);
  76.     ll m, n;
  77.     cin >> m >> n;
  78.     a[0] = 0;
  79.     for (int i = 1; i <= n; i++)
  80.         cin >> a[i];
  81.     ++n;
  82.     sort(a, a + n);
  83.     cout << solve(n, m);
  84. }
  85.  
Time limit exceeded #stdin #stdout 5s 16016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/etrMiI
language:
C++14 (gcc 8.3)
created:
6 years 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!