https://codeforces.net/problemset/problem/1250/B

this problem has no editorial. i just iterated all possible r and calculate minimum s with binary search

doing binary search, i greedily tried to take two teams at one ride if it's possible. if s is fixed and current team has c member, i checked whether there's a team with maximum number of members d <= (s-c) if there's such team, two team can ride together, otherwise just take one time at this ride.

is it logically wrong? or implementation is wrong? need help! (also i wanna know if there's a solution with complexity k^2 or faster , since my code is too slow )

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef pair<int,int> pi; vectorarr; bool pos(ll s,ll ride){ if(s<arr.back()) return 0; ll r = 0; multisetst(arr.begin(),arr.end()); while(st.size()){ r++; int cur = *st.begin(); if(cur>s) return 0; st.erase(st.begin()); if(st.size()==0) break; auto it = st.upper_bound(s-cur); if(it==st.begin()) continue; st.erase(prev(it)); } return r<=ride; } ll f(ll ride){ ll l = 0; ll r = INT32_MAX; while(l<=r){ ll mid = (l+r)>>1; if(!pos(mid,ride)) l = mid+1; else r = mid-1; } return ride*l; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; map<int,int>m; for(int i=1; i<=n; i++){ int a; cin>>a; m[a]++; } for(auto p : m) arr.push_back(p.second); sort(arr.begin(),arr.end()); if(arr.size()==1){ cout<<arr.back(); return 0; } ll ans = INT64_MAX; for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){ ans = min(ans,f(i)); } cout<<ans; }