QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364460 | #6401. Classic: N Real DNA Pots | Z-wzy | TL | 0ms | 0kb | C++14 | 1.1kb | 2024-03-24 14:38:11 | 2024-03-24 14:38:11 |
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] *= 10000000;
}
long long l = -1e9, r = 1e9;
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;
}
/*
2 2
222640995 547139825
489207317 725361095
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 3 1 2 2 4 3 3 4 1