QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #470409 | #6401. Classic: N Real DNA Pots | UESTC_xxx# | TL | 2ms | 10120kb | C++20 | 1.0kb | 2024-07-10 12:58:48 | 2024-07-10 12:58:48 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
int n,k;
double eps=1e-14,g[500005],a[500005];
int f[500005];
struct node{
ll x,y;
}p[500005];
bool check(double x){
for(int i=1;i<=n;++i) a[i]=p[i].y-x*p[i].x,g[i]=1e18+1;
f[1]=1;
g[1]=a[1];
g[0]=-1e18-1;
int cnt=1;
for(int i=2;i<=n;++i){
int l=0,r=cnt+1;
while(l<r){
int mid=(l+r)/2;
if(g[mid]<=a[i]) l=mid+1;
else r=mid;
}
/* while(g[l+1]<=a[i]) l++;
while(g[l]>a[i]) l--;
l++;*/
f[i]=l;
g[l]=min(g[l],a[i]);
cnt=max(cnt,f[i]);
}
if(cnt>=k) return 1;
return 0;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&p[i].x,&p[i].y);
}
double l=-1e10,r=1e10;
while(l+eps<r){
double mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.14lf",l);
}
/*
4 4
1 2
2 4
3 3
4 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10084kb
input:
4 3 1 2 2 4 3 3 4 1
output:
-1.00000000000000
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 10048kb
input:
2 2 1 1 5 3
output:
0.50000000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 10032kb
input:
2 2 222640995 547139825 489207317 725361095
output:
0.66858134464562
result:
ok found '0.6685813', expected '0.6685813', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 10120kb
input:
1000 20 545612 774435015 828317 212155588 5294705 85926095 5648835 764528941 6159263 570820268 7177330 744079287 8446124 162286636 8735551 586528841 9263030 524140841 9505706 636254627 12111352 182639083 12750780 238494418 13149143 913232250 13382784 11485121 13699797 414697815 14263990 423817548 15...
output:
3.79321046228665
result:
ok found '3.7932105', expected '3.7932105', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 10056kb
input:
1000 100 163505 684865289 2674260 837752883 2694530 150054425 2870791 236723512 3262597 800933455 3558503 905056977 4260872 45990808 4532415 268478572 5299228 546172100 6019224 12074540 6345109 747272172 6539452 449655551 7215852 676269961 9062989 769545718 9444242 874911191 10264016 341805234 10595...
output:
-1.86057787604184
result:
ok found '-1.8605779', expected '-1.8605779', error '0.0000000'
Test #6:
score: -100
Time Limit Exceeded
input:
5000 10 34774 620025564 366562 278306777 446710 509672662 650220 70882120 824803 317731338 881144 257861254 1063458 61483347 1071840 639872836 1263842 30790337 1591940 346781076 1964777 814735151 2067497 63962255 2220071 379252135 2539054 428050443 2937092 423099578 3088992 959927412 3229098 9591796...