oj.uz

Submission #654729

# Submission time Handle Problem Language Result Execution time Memory
654729 2022-11-01T11:40:32 Z pauloamed Sure Bet (CEOI17_sure) C++14
0 / 100
 1 ms 324 KB 
#include<bits/stdc++.h>
using namespace std;

#define ld double

vector<ld> sa, sb;

ld ternary_search(int l, int r, ld a, int b) {
  auto f = [&](int j){
    return min(sb[j], a) - (b + j + 1);
  };

  while (r - l >= 3) {
    int m1 = l + (r - l) / 3;
    int m2 = r - (r - l) / 3;
    int f1 = f(m1), f2 = f(m2);
    if(f1 < f2) l = m1;
    else r = m2;
  }

  ld ans = 0;
  while(l <= r) ans = max(ans, f(l++));
  return ans;
}

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  int n; cin >> n;
  vector<ld> a, b;
  for(int i = 0; i < n; ++i){
    ld x, y; cin >> x >> y;
    a.push_back(x);
    b.push_back(y);
  }

  sort(a.rbegin(), a.rend());
  sort(b.rbegin(), b.rend());

  
  for(int i = 0; i < n; ++i){
    sa.push_back(a[i]);
    sb.push_back(b[i]);
    if(i){
      sa[i] += sa[i - 1];
      sb[i] += sb[i - 1];
    }
  }

  ld ans = 0;
  for(int i = 0; i < n; ++i){
    ans = max(ans, ternary_search(0, n - 1, sa[i], (i + 1)));
  }
  cout << setprecision(4) << fixed << ans << "\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 324 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 324 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 324 KB Output isn't correct
7 Halted 0 ms 0 KB -