SHARE
TWEET

Untitled

a guest Oct 28th, 2019 116 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #define mt make_tuple
  5. #define ll long long
  6. #define eb emplace_back
  7. #define fi first
  8. #define pb push_back
  9. #define all(x) (x).begin(), (x).end()
  10. #define rall(x) (x).rbegin(), (x).rend()
  11. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  12. #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
  13. #define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
  14. #define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
  15. #define mod(a,b) ((a%b +b)%b)
  16. #define bit(x,i) (x&(1<<i))  //select the bit of position i of x
  17. #define lowbit(x) ((x)&((x)^((x)-1))) //get the lowest bit of x
  18. #define hBit(msb,n) asm("bsrl %1,%0" : "=r"(msb) : "r"(n)) //get the highest bit of x, maybe the fastest
  19. #define max(a,b) (a<b?b:a)
  20. #define min(a,b) (a>b?b:a)
  21. #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  22. #define IN(i,l,r) (l<i&&i<r)
  23. #define LINR(i,l,r) (l<=i&&i<=r)
  24. #define LIN(i,l,r) (l<=i&&i<r)
  25. #define INR(i,l,r) (l<i&&i<=r)
  26. #define lastEle(vec) vec[vec.size()-1]
  27. #define SZ(x) ((int)((x).size()))
  28. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  29. #define ll long long
  30. #define ull unsigned long long
  31. #define ui unsigned int
  32. #define us unsigned short
  33. #define INF 1001001001
  34. #define PI 3.1415926535897932384626
  35.  
  36. using namespace std;
  37.  using namespace __gnu_pbds;
  38.  template <typename T>
  39.  using ordered_set =
  40.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  41.  
  42. typedef pair<int, int> pii;
  43. typedef vector<int> vi;
  44. typedef vector<pii> vpi;
  45. typedef vector<vi> vvi;
  46.  
  47. void err(istream_iterator<string> it) {}
  48. template<typename T, typename... Args>
  49. void err(istream_iterator<string> it, T a, Args... args) {
  50.     cerr << *it << " = " << a << endl;
  51.     err(++it, args...);
  52. }
  53.  
  54. //----------------------------------------------------------------------------------------------------------------------
  55.  
  56.  
  57. void swap(char &a, char & b){
  58.     char temp = a;
  59.     a = b;
  60.     b = temp;
  61. }
  62.  
  63. const ll MOD = 998244353;
  64. const int MAXN = 1e5 + 5;
  65.  
  66. //char grid[MAXN][MAXN];
  67.  
  68. void add_self(ll &a, ll b){
  69.     a+= b;
  70.     while(a > MOD){
  71.         a-=MOD;
  72.     }
  73. }
  74.  
  75.  
  76. ll inf = 1LL*1e18;
  77.  
  78. void no(){
  79.     cout <<"NO" << endl;
  80.     exit(0);
  81. }
  82.  
  83. void yes(){
  84.     cout <<"YES" << endl;
  85.     exit(0);
  86. }
  87.  
  88. ll getAns(ll mx,vector< ll > & arr){
  89.     int l = 0; int r = arr.size() - 1;
  90.     ll ride = 0;
  91.     while( l <= r){
  92.         if(mx < arr[l]) return inf;
  93.         if(arr[r] > mx) return inf;
  94.         if(l == r){
  95.             ride++;
  96.             l++; r--;
  97.         }else{
  98.             if(arr[l] + arr[r] > mx){
  99.                 r--;
  100.             }else{
  101.                 l++; r--;
  102.             }
  103.             ride++;
  104.         }
  105.     }
  106.     return ride*mx;
  107. }
  108.  
  109. int main(){
  110.     int n;
  111.     cin >> n;
  112.     int k;
  113.     cin >> k;
  114.     vector< ll > arr (k);
  115.     for(int i = 0;i < n;i++){
  116.         int t; scanf("%d",&t); t--;
  117.         arr[t]++;
  118.     }
  119.     ll ans = inf;
  120.     sort(all(arr));
  121.  
  122.     ll mx = 0;
  123.     ll left = 1; ll right = arr[k-1];
  124.     if(k > 1) right += arr[k-2];
  125.     for(ll i = 0;i < (k/2);i++){
  126.         ll curr = arr[i] + arr[k - i - 1];
  127.         ans = min(ans,getAns(curr, arr));
  128.     }
  129.     ans = min(ans,getAns(arr[k-1],arr));
  130.     cout << ans << endl;
  131.     return 0;
  132. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top