UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173856#8. 小w、小j和小zzhzhallen0708ms1296kbC++1.3kb2023-07-20 17:20:202023-07-20 17:20:22

answer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
const int eps = 1e-8;
const int INF = 1e9 +10;

struct people {
    int p,v,tmp;
} f[N];
long double g[N];

int n,k;

bool cmp(people A,people B)
{
    return A.p < B.p;
}
bool cmp1(people A,people B)
{
    return A.tmp < B.tmp;
}
int check(double mid){
    for (int i = 1; i <= n; i ++ )
        f[i].tmp = f[i].p + f[i].v*mid;
    sort(f + 1, f + n + 1,cmp);  
    int t = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if(!t || g[t] < f[i].tmp) g[++ t] = f[i].tmp;  
        if(t && fabs(g[t]-f[i].tmp) < eps) continue;  
        g[upper_bound(g + 1, g + t + 1,f[i].tmp)-g] = f[i].tmp;  
    }
    return t + k >= n;  
}



int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )
    {
        int p,v;
        cin >> p >> v;
        f[i] = (people){p,v};
    }
    
    sort(f + 1,f + 1 + n, cmp);
    
    
    double l = 0,r = INF + 1,mid;
    for(int i = 1; i <= log2(INF)*log2(INF); i ++ ) {
        mid = (l + r)/2.0;
        if(check(mid)) l = mid;
        else r = mid;
    }

    if(mid > INF/5) return puts("FOREVER"),0;
    return printf("%.4lf",mid),0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

20 10
-715624307 -28629151
957936621 17210368
-753657459 59049
-40974960 5153632
-402454312 -3450252...

output:

11.3999

result:

ok answer is 11.3999000000

Test #2:

score: 0
Accepted
time: 1ms
memory: 1248kb

input:

20 7
-715624307 -310
957936621 3
-753657459 1
-40974960 5
-402454312 -7424
874144191 -4
-227392025 7...

output:

5850568.4000

result:

ok answer is 5850568.5000000000

Test #3:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

20 4
-715624307 -1
957936621 3
-753657459 6
-40974960 1
-402454312 -1
874144191 -2
-227392025 9
-808...

output:

3926259.5000

result:

ok answer is 3926260.0000000000

Test #4:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

20 6
-715624307 -1
957936621 3
-753657459 1
-40974960 1
-402454312 -119
874144191 -1
-227392025 359
...

output:

9635550.7692

result:

ok answer is 9635550.8333000001

Test #5:

score: -10
Wrong Answer
time: 0ms
memory: 1240kb

input:

20 10
-715624307 740210959
-955556582 -615695756
-24759231 771301784
-80855559 560021841
-892686343 ...

output:

2.4534

result:

wrong answer Wrong answer!

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 20
Accepted
time: 9ms
memory: 1244kb

input:

200 10
-487405787 3200000
725249085 28629151
-671026855 -4084101
38046635 45435424
-188495128 643634...

output:

0.0039

result:

ok answer is 0.0039000000

Test #7:

score: 0
Accepted
time: 9ms
memory: 1244kb

input:

200 10
-487405787 1
725249085 65536
-671026855 -100000000
38046635 1679616
-188495128 6561
-73172885...

output:

0.0042

result:

ok answer is 0.0041000000

Test #8:

score: 0
Accepted
time: 9ms
memory: 1248kb

input:

200 10
-487405787 3
725249085 2
-671026855 -6
38046635 5
-188495128 14
-731728859 12
-331220744 2
31...

output:

14398.5166

result:

ok answer is 14398.5188000000

Test #9:

score: 0
Accepted
time: 9ms
memory: 1252kb

input:

200 10
-487405787 56
725249085 2
-671026855 -8
38046635 1
-188495128 252
-731728859 28
-331220744 2
...

output:

8320.3680

result:

ok answer is 8320.3684000000

Test #10:

score: 0
Accepted
time: 9ms
memory: 1248kb

input:

200 10
-487405787 11
725249085 8
-671026855 -1
38046635 1
-188495128 125
-731728859 106
-331220744 4...

output:

543.5187

result:

ok answer is 543.5186000000

Test #11:

score: -20
Wrong Answer
time: 9ms
memory: 1240kb

input:

200 10
-584283703 -467650291
-389608337 -287739809
-372147316 -257836606
175915600 328991856
7355243...

output:

1.1755

result:

wrong answer Wrong answer!

Subtask #3:

score: 0
Skipped

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 15
Accepted
time: 108ms
memory: 1296kb

input:

2000 10
882856800 -387420489
866607093 -134217728
481381898 1
-488180557 1953125
-783185249 -19683
-...

output:

0.0002

result:

ok answer is 0.0001000000

Test #19:

score: 0
Accepted
time: 108ms
memory: 1292kb

input:

2000 10
882856800 -177147
866607093 -48828125
481381898 1
-488180557 48828125
-783185249 -362797056
...

output:

0.0001

result:

ok answer is 0.0001000000

Test #20:

score: 0
Accepted
time: 107ms
memory: 1288kb

input:

2000 10
882856800 -1
866607093 -396
481381898 21
-488180557 6
-783185249 -10
-816111307 -33761
99248...

output:

2.6236

result:

ok answer is 2.6237000000

Test #21:

score: 0
Accepted
time: 119ms
memory: 1296kb

input:

2000 10
882856800 -3
866607093 -2
481381898 12
-488180557 8639109
-783185249 -12
-816111307 -96
9924...

output:

0.0008

result:

ok answer is 0.0008000000

Test #22:

score: 0
Accepted
time: 104ms
memory: 1296kb

input:

2000 10
882856800 -1
866607093 -10
481381898 406927
-488180557 1
-783185249 -1483
-816111307 -8
9924...

output:

0.0003

result:

ok answer is 0.0003000000

Test #23:

score: -15
Wrong Answer
time: 107ms
memory: 1288kb

input:

2000 10
784172079 808971860
81381899 71917076
-712636352 -738530531
-622770179 -640667385
119667134 ...

output:

1.1482

result:

wrong answer Wrong answer!

Subtask #5:

score: 0
Skipped

Subtask #6:

score: 0
Skipped