UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#148672#8. 小w、小j和小zCodingShark106ms1284kbC++1.0kb2022-07-15 09:45:102022-07-15 09:45:11

answer

#include <bits/stdc++.h>
using namespace std;
int n, k;
double rec[100005];
struct node
{
    int p, v;
    bool operator<(const node t) const
    {
        return p == t.p ? v > t.v : p < t.p;
    }
} a[100005];

bool check(double x)
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        double v = a[i].p + a[i].v * x;
        int pos = lower_bound(rec + 1, rec + ans + 1, v) - rec;
        rec[pos] = v, ans = max(ans, pos);
    }
    return n - ans <= k;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
#endif
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &a[i].p, &a[i].v);
    sort(a + 1, a + n + 1);
    double l = 0, r = 1e9;
    while (r - l > 1e-5)
    {
        double mid = (l + r) / 2.0;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    if (l > 1e8)
        puts("Forever");
    else
        printf("%.2lf", l);
    return 0;
}

Details

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

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

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

output:

11.40

result:

ok answer is 11.3999000000

Test #2:

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

input:

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

output:

5850568.50

result:

ok answer is 5850568.5000000000

Test #3:

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

input:

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

output:

3926260.00

result:

ok answer is 3926260.0000000000

Test #4:

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

input:

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

output:

9635550.83

result:

ok answer is 9635550.8333000001

Test #5:

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

input:

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

output:

Forever

result:

ok OK, forever!

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 1256kb

input:

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

output:

0.00

result:

wrong answer expected 0.0039000000, found 0.0000000000

Subtask #3:

score: 0
Skipped

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 15
Accepted
time: 2ms
memory: 1284kb

input:

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

output:

0.00

result:

ok answer is 0.0001000000

Test #19:

score: 0
Accepted
time: 4ms
memory: 1284kb

input:

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

output:

0.00

result:

ok answer is 0.0001000000

Test #20:

score: -15
Wrong Answer
time: 0ms
memory: 1280kb

input:

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

output:

2.62

result:

wrong answer expected 2.6237000000, found 2.6200000000

Subtask #5:

score: 0
Skipped

Subtask #6:

score: 0
Skipped