QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364471 | #6401. Classic: N Real DNA Pots | Z-wzy | WA | 0ms | 5984kb | C++14 | 1.0kb | 2024-03-24 14:42:23 | 2024-03-24 14:42:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long n, m, a[N], b[N];
__int128_t op;
int ok(long long x){
vector<__int128_t> g;
for(int i=1;i<=n;i++){
op = b[i] - a[i] * x;
if(g.size() == 0 || g.back() <= op){
g.push_back(op);
}
else{
g[upper_bound(g.begin(),g.end(),op)-g.begin()] = op;
}
if(g.size() == m){
return 1;
}
}
return 0;
}
void run(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
cin >> b[i];
b[i] *= 10000000;
}
long long l = -1e17, r = 1e17;
while(l < r){
long long mid = (l + r) / 2;
if(ok(mid)){
l = mid + 1;
}
else{
r = mid;
}
}
l --;
double ans = l;
ans /= 10000000;
printf("%.7lf\n",ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
run();
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5948kb
input:
4 3 1 2 2 4 3 3 4 1
output:
-1.0000000
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
2 2 1 1 5 3
output:
0.5000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 5984kb
input:
2 2 222640995 547139825 489207317 725361095
output:
2753756214.5640244
result:
wrong answer 1st numbers differ - expected: '0.6685813', found: '2753756214.5640244', error = '2753756213.8954430'