# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
800982 |
2023-08-02T03:26:04 Z |
vjudge1 |
Sure Bet (CEOI17_sure) |
C++11 |
|
73 ms |
3456 KB |
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <deque>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <iomanip>
using namespace std;
using lli = long long;
using ldb = long double;
const int maxN = 1e5;
ldb a[maxN + 1];
ldb b[maxN + 1];
ldb ps[maxN + 1];
int n;
ldb Calc(ldb resa, ldb resb, int pb)
{
if (resb >= resa)
return resb;
int low = pb;
int high = n;
while (low <= high)
{
int mid = (low + high) / 2;
if (resa - (mid - pb + 1) >= resb + ps[mid] - ps[pb - 1] - (mid - pb + 1))
low = mid + 1;
else
high = mid - 1;
}
--low;
resa -= (low - pb + 1);
resb += ps[low] - ps[pb - 1] - (low - pb + 1);
ldb res = resb;
if (low < n)
res = max(res, resa - 1);
return res;
}
int main()
{
#ifdef LeMinhDuc
freopen("inp.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i] >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
ldb ans = 0;
int cnt = 0;
ldb resa = 0;
ldb resb = 0;
int c1 = n;
int c2 = n;
while(true)
{
if (c1 == 0 && c2 == 0) break;
if(c1 == 0)
{
resb += b[c2];
c2--;
cnt++;
}
else if(c2 == 0)
{
resa += a[c1];
c1--;
cnt++;
}
else if (resa < resb)
{
resa += a[c1];
c1--;
cnt++;
}
else if (resa > resb)
{
resb += b[c2];
c2--;
cnt++;
}
else if (resa == resb)
{
if (c2 == 0 || a[c1] > b[c2])
{
resa += a[c1];
c1--;
cnt++;
}
else if(c1 == 0 || a[c1] <= b[c2])
{
resb += b[c2];
c2--;
cnt++;
}
}
long double res = min(resa - cnt , resb - cnt);
ans = max(ans , res);
}
cout<<fixed << setprecision(4) <<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 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 |
67 ms |
3456 KB |
Output is correct |
18 |
Correct |
65 ms |
3424 KB |
Output is correct |
19 |
Correct |
66 ms |
3424 KB |
Output is correct |
20 |
Correct |
67 ms |
3448 KB |
Output is correct |
21 |
Correct |
70 ms |
3404 KB |
Output is correct |
22 |
Correct |
65 ms |
3424 KB |
Output is correct |
23 |
Correct |
73 ms |
3448 KB |
Output is correct |
24 |
Correct |
65 ms |
3332 KB |
Output is correct |
25 |
Correct |
67 ms |
3448 KB |
Output is correct |
26 |
Correct |
72 ms |
3436 KB |
Output is correct |