oj.uz

Submission #987312

# Submission time Handle Problem Language Result Execution time Memory
987312 2024-05-22T14:38:36 Z huutuan Sails (IOI07_sails) C++14
30 / 100
 18 ms 5464 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3420 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5212 KB Output is correct
2 Correct 15 ms 4696 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 5464 KB Output isn't correct
2 Halted 0 ms 0 KB -