UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#159019#8. 小w、小j和小zwuzr024ms2156kbC++1.2kb2022-08-28 18:55:182022-08-28 18:55:19

answer

#include<bits/stdc++.h>
using namespace std;
#define re register
#define rep(i,a,b) for(ll i(a);i<=b;++i)
#define per(i,a,b) for(ll i(a);i>=b;--i)
#define ll long long
#define swap(x,y) x^=y^=x^=y
#define y1 yyy1
#define int ll
struct node {
	int p, v;
} a[100005];
int n, k;
int dp[100005];
double pos[100005], low[100005];
bool ck(double x) {
	rep(i, 1, n) pos[i] = a[i].p + a[i].v * x;
	memset(dp, 0, sizeof dp);
	int mx = 0;
	low[0] = -9e18;
	rep(i, 1, n) {
		dp[i] = upper_bound(low, low + mx + 1, pos[i] - 1e-7) - low;
		if (dp[i] > mx) {
			mx = dp[i];
			low[mx] = pos[i];
		} else low[dp[i]] = max(low[dp[i]], pos[i]);
	}
	return mx + k >= n;
}
bool cmp(node x, node y) {
	if (x.p == y.p) return x.v > y.v;
	else return x.p < y.p;
}
signed main() {
	ios::sync_with_stdio(0);
	cin >> n >> k;
	rep(i, 1, n) cin >> a[i].p >> a[i].v;
	sort(a + 1, a + n + 1, cmp);
	int t = 1;
	rep(i, 2, n) {
		if (a[i].p == a[t].p && a[i].v == a[t].v) k--;
		else a[++t] = a[i];
	}
	n = t;
	double l = 0, r = 2.5e9;
	while (l + 1e-7 < r) {
		double mid = (l + r) / 2;
		if (ck(mid)) l = mid;
		else r = mid;
	}
	double ans = (l + r) / 2;
	if (ans > 2.4e9) puts("Forever");
	else printf("%.6lf", ans);
	return 0;
}

详细

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 2088kb

input:

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

output:

1.264558

result:

wrong answer expected 11.3999000000, found 1.2645580000

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 20
Accepted
time: 0ms
memory: 2096kb

input:

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

output:

0.003057

result:

ok answer is 0.0039000000

Test #7:

score: 0
Accepted
time: 3ms
memory: 2092kb

input:

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

output:

0.004186

result:

ok answer is 0.0041000000

Test #8:

score: -20
Wrong Answer
time: 4ms
memory: 2100kb

input:

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

output:

11602.228070

result:

wrong answer expected 14398.5188000000, found 11602.2280700000

Subtask #3:

score: 0
Skipped

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 15
Accepted
time: 6ms
memory: 2156kb

input:

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

output:

0.000167

result:

ok answer is 0.0001000000

Test #19:

score: 0
Accepted
time: 6ms
memory: 2156kb

input:

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

output:

0.000114

result:

ok answer is 0.0001000000

Test #20:

score: -15
Wrong Answer
time: 3ms
memory: 2152kb

input:

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

output:

0.009964

result:

wrong answer expected 2.6237000000, found 0.0099640000

Subtask #5:

score: 0
Skipped

Subtask #6:

score: 0
Skipped