Submission #987312

#	Time	Username	Problem	Language	Result	Execution time	Memory
987312		huutuan	Sails (IOI07_sails)	C++14	30 / 100	18 ms	5464 KiB

sails

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e5+10;
int n;
int a[N], b[N], cnt[N], aa[N], bb[N];

bool check(int mid){
   for (int i=1; i<=n; ++i) a[i]=aa[i], b[i]=bb[i];
   int len=0;
   for (int i=N-1; i>=1; --i) if (cnt[i]<mid) len=i;
   for (int i=1; i<=n; ++i) b[i]-=max(0ll, a[i]-len+1);
   --len;
   int sum=0;
   for (int i=1; i<=n; ++i){
      if (b[i]>len) return 0;
      sum+=max(0ll, b[i]);
   }
   return sum<=len*mid;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> aa[i] >> bb[i], a[i]=aa[i], b[i]=bb[i], ++cnt[a[i]];
   for (int i=N-2; i>=0; --i) cnt[i]+=cnt[i+1];
   int l=1, r=n;
   while (l<=r){
      int mid=(l+r)>>1;
      if (check(mid)) r=mid-1;
      else l=mid+1;
   }
   int mid=l;
   for (int i=1; i<=n; ++i) a[i]=aa[i], b[i]=bb[i];
   int len=0, ans=0;
   for (int i=N-1; i>=1; --i) if (cnt[i]<mid) len=i;
   for (int i=1; i<=n; ++i) b[i]-=max(0ll, a[i]-len+1);
   for (int i=len; i<N; ++i) ans+=cnt[i]*(cnt[i]-1)/2;
   int sum=0;
   for (int i=1; i<=n; ++i){
      if (b[i]>len) return 0;
      sum+=max(0ll, b[i]);
   }
   --len;
   if (len){
      int rem=sum%len;
      ans+=(mid-1)*(mid-2)/2*(len-rem);
      ans+=mid*(mid-1)/2*rem;
   }
   cout << ans << '\n';
   return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10