QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605336 | #6401. Classic: N Real DNA Pots | lqh2024# | WA | 0ms | 3928kb | C++17 | 1.9kb | 2024-10-02 16:45:02 | 2024-10-02 16:45:03 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);
void QAQ() {
int n, v;
cin >> n >> v;
vector<array<int, 2>> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i][0] >> a[i][1];
}
double l = -2e9, r = 2e9;
auto chk = [&](double k) {
int res = 1;
map<double, int> q;
for (int i = 1; i <= n; i++) {
double t = a[i][1] - k * a[i][0];
auto it = q.upper_bound(t);
if (it != q.begin()) {
it = prev(it);
int now = it -> second + 1;
res = max(res, now);
it = q.lower_bound(t);
while (it != q.end() && it -> second <= now) {
it = q.erase(it);
}
q.insert({a[i][1] - k * a[i][0], now});
} else {
q.insert({a[i][1] - k * a[i][0], 1});
}
}
return res >= v;
};
for (int i = 0; i < 50; i++) {
auto mid = (l + r) / 2;
if (chk(mid)) {
l = mid;
} else {
r = mid;
}
}
cout << l << "\n";
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1;
// cin >> t;
for (cout << fixed << setprecision(12); t--; QAQ());
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
4 3 1 2 2 4 3 3 4 1
output:
-1.000000082740
result:
ok found '-1.0000001', expected '-1.0000000', error '0.0000001'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3928kb
input:
2 2 1 1 5 3
output:
0.499998265013
result:
wrong answer 1st numbers differ - expected: '0.5000000', found: '0.4999983', error = '0.0000017'