답안 #537927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537927	2022-03-15T21:59:00 Z	theysoldtheworld	Sure Bet (CEOI17_sure)	C++14	100 / 100	105 ms	5804 KB

sure

#include <bits/stdc++.h>
 
using namespace std;
 
double Get(vector<double> a , vector<double> b) {
  int n = (int)a.size();
  double h = 0;
  double ans = 0;
  vector<double> pref(n);
  for (int i = 0 ; i < n ; i++) {
    pref[i] = (i > 0 ? pref[i - 1] : 0) + b[i];
  }
  auto F = [&](int mid , int i) {
    return min(h - (mid + 1) , pref[mid] - (i + 1));
  };
  int last_pos = -1;
  for (int i = 0 ; i < n ; i++) {
    h += a[i];
    int l = -1 , r = n;
    while (r - l > 1) {
      int mid = l + (r - l) / 2;
      if (F(mid , i) > F(mid + 1 , i)) {
        r = mid;
      }
      else {
        l = mid;
      }
    }
    assert(l + 1 >= last_pos);
    last_pos = l + 1;
    ans = max(ans , F(l + 1 , i));
  }
  return ans;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<double> a(n) , b(n);
  for (int i = 0 ; i < n ; i++) {
    cin >> a[i] >> b[i];
    a[i] -= 1; 
    b[i] -= 1;
  }
  sort(a.rbegin() , a.rend());
  sort(b.rbegin() , b.rend());
  double ans = max(Get(a , b) , Get(b , a));
  cout << fixed << setprecision(4) << ans << '\n';
  return 0; 
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	284 KB	Output is correct

Subtask #2

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	284 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	284 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	96 ms	5704 KB	Output is correct
18	Correct	98 ms	5704 KB	Output is correct
19	Correct	102 ms	5708 KB	Output is correct
20	Correct	105 ms	5716 KB	Output is correct
21	Correct	100 ms	5708 KB	Output is correct
22	Correct	96 ms	5720 KB	Output is correct
23	Correct	100 ms	5804 KB	Output is correct
24	Correct	98 ms	5724 KB	Output is correct
25	Correct	99 ms	5704 KB	Output is correct
26	Correct	105 ms	5788 KB	Output is correct