Submission #537916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
537916	2022-03-15T21:37:45 Z	theysoldtheworld	Sure Bet (CEOI17_sure)	C++14	100 / 100	107 ms	7552 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));
  };
  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;
      }
    }
    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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 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	1 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	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 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	1 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	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	97 ms	5760 KB	Output is correct
18	Correct	99 ms	7236 KB	Output is correct
19	Correct	99 ms	7072 KB	Output is correct
20	Correct	104 ms	7100 KB	Output is correct
21	Correct	103 ms	7484 KB	Output is correct
22	Correct	98 ms	7168 KB	Output is correct
23	Correct	99 ms	7116 KB	Output is correct
24	Correct	97 ms	7176 KB	Output is correct
25	Correct	100 ms	7100 KB	Output is correct
26	Correct	107 ms	7552 KB	Output is correct