Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define mt make_tuple
- #define ll long long
- #define eb emplace_back
- #define fi first
- #define pb push_back
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
- #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
- #define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
- #define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
- #define mod(a,b) ((a%b +b)%b)
- #define bit(x,i) (x&(1<<i)) //select the bit of position i of x
- #define lowbit(x) ((x)&((x)^((x)-1))) //get the lowest bit of x
- #define hBit(msb,n) asm("bsrl %1,%0" : "=r"(msb) : "r"(n)) //get the highest bit of x, maybe the fastest
- #define max(a,b) (a<b?b:a)
- #define min(a,b) (a>b?b:a)
- #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
- #define IN(i,l,r) (l<i&&i<r)
- #define LINR(i,l,r) (l<=i&&i<=r)
- #define LIN(i,l,r) (l<=i&&i<r)
- #define INR(i,l,r) (l<i&&i<=r)
- #define lastEle(vec) vec[vec.size()-1]
- #define SZ(x) ((int)((x).size()))
- #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
- #define ll long long
- #define ull unsigned long long
- #define ui unsigned int
- #define us unsigned short
- #define INF 1001001001
- #define PI 3.1415926535897932384626
- using namespace std;
- using namespace __gnu_pbds;
- template <typename T>
- using ordered_set =
- tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef vector<pii> vpi;
- typedef vector<vi> vvi;
- void err(istream_iterator<string> it) {}
- template<typename T, typename... Args>
- void err(istream_iterator<string> it, T a, Args... args) {
- cerr << *it << " = " << a << endl;
- err(++it, args...);
- }
- //----------------------------------------------------------------------------------------------------------------------
- void swap(char &a, char & b){
- char temp = a;
- a = b;
- b = temp;
- }
- const ll MOD = 998244353;
- const int MAXN = 1e5 + 5;
- //char grid[MAXN][MAXN];
- void add_self(ll &a, ll b){
- a+= b;
- while(a > MOD){
- a-=MOD;
- }
- }
- ll inf = 1LL*1e18;
- void no(){
- cout <<"NO" << endl;
- exit(0);
- }
- void yes(){
- cout <<"YES" << endl;
- exit(0);
- }
- ll getAns(ll mx,vector< ll > & arr){
- int l = 0; int r = arr.size() - 1;
- ll ride = 0;
- while( l <= r){
- if(mx < arr[l]) return inf;
- if(arr[r] > mx) return inf;
- if(l == r){
- ride++;
- l++; r--;
- }else{
- if(arr[l] + arr[r] > mx){
- r--;
- }else{
- l++; r--;
- }
- ride++;
- }
- }
- return ride*mx;
- }
- int main(){
- int n;
- cin >> n;
- int k;
- cin >> k;
- vector< ll > arr (k);
- for(int i = 0;i < n;i++){
- int t; scanf("%d",&t); t--;
- arr[t]++;
- }
- ll ans = inf;
- sort(all(arr));
- ll mx = 0;
- ll left = 1; ll right = arr[k-1];
- if(k > 1) right += arr[k-2];
- for(ll i = 0;i < (k/2);i++){
- ll curr = arr[i] + arr[k - i - 1];
- ans = min(ans,getAns(curr, arr));
- }
- ans = min(ans,getAns(arr[k-1],arr));
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement