Submission #654732

#	Time	Username	Problem	Language	Result	Execution time	Memory
654732		pauloamed	Sure Bet (CEOI17_sure)	C++14	100 / 100	94 ms	6040 KiB

sure

#include<bits/stdc++.h>
using namespace std;

#define ld double

vector<ld> sa, sb;

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

  while (hi - lo > 1){
    int mid = (hi + lo)>>1;
    if (f(mid) > f(mid + 1)) 
      hi = mid;
    else 
      lo = mid; 
  }
  return f(lo + 1);
}

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];
    }
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      ld x = min(sa[i], sb[j]);
      int y = i + j + 2;
    }
  }

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

Compilation message (stderr)

sure.cpp: In function 'int32_t main()':
sure.cpp:48:10: warning: unused variable 'x' [-Wunused-variable]
   48 |       ld x = min(sa[i], sb[j]);
      |          ^
sure.cpp:49:11: warning: unused variable 'y' [-Wunused-variable]
   49 |       int y = i + j + 2;
      |           ^

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40