QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364447 | #6401. Classic: N Real DNA Pots | Z-wzy | TL | 0ms | 0kb | C++14 | 1023b | 2024-03-24 14:34:13 | 2024-03-24 14:34:14 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long n, m, a[N], b[N], op;
int ok(long long x){
vector<long long> 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] *= 100000000;
}
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 /= 100000000;
printf("%.7lf\n",ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
run();
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
4 3 1 2 2 4 3 3 4 1