UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#159021#8. 小w、小j和小zwuzr1003919ms6704kbC++1.3kb2022-08-28 18:58:222022-08-28 18:58:24

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
#define double long double
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]] = min(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;
}

Details

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

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 3ms
memory: 2088kb

input:

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

output:

11.399931

result:

ok answer is 11.3999000000

Test #2:

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

input:

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

output:

5850568.500000

result:

ok answer is 5850568.5000000000

Test #3:

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

input:

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

output:

3926260.000000

result:

ok answer is 3926260.0000000000

Test #4:

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

input:

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

output:

9635550.833333

result:

ok answer is 9635550.8333000001

Test #5:

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

input:

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

output:

Forever

result:

ok OK, forever!

Subtask #2:

score: 20
Accepted

Test #6:

score: 20
Accepted
time: 2ms
memory: 2092kb

input:

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

output:

0.003931

result:

ok answer is 0.0039000000

Test #7:

score: 0
Accepted
time: 1ms
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: 0
Accepted
time: 1ms
memory: 2096kb

input:

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

output:

14398.518868

result:

ok answer is 14398.5188000000

Test #9:

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

input:

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

output:

8320.368421

result:

ok answer is 8320.3684000000

Test #10:

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

input:

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

output:

543.518678

result:

ok answer is 543.5186000000

Test #11:

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

input:

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

output:

Forever

result:

ok OK, forever!

Subtask #3:

score: 15
Accepted

Test #12:

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

input:

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

output:

0.035919

result:

ok answer is 0.0359000000

Test #13:

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

input:

200 100
-487405787 690807104
725249085 2685619
-671026855 -18399744
38046635 862801408
-188495128 54...

output:

0.128752

result:

ok answer is 0.1288000000

Test #14:

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

input:

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

output:

3184277.230769

result:

ok answer is 3184277.2307000002

Test #15:

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

input:

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

output:

572916.761905

result:

ok answer is 572916.7619000000

Test #16:

score: 0
Accepted
time: 2ms
memory: 2100kb

input:

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

output:

7362.450593

result:

ok answer is 7362.4506000000

Test #17:

score: 0
Accepted
time: 5ms
memory: 2044kb

input:

200 75
-584283703 -510093529
-389608337 -734253121
-372147316 -257836606
175915600 -355171217
735524...

output:

Forever

result:

ok OK, forever!

Subtask #4:

score: 15
Accepted

Test #18:

score: 15
Accepted
time: 12ms
memory: 2184kb

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: 8ms
memory: 2180kb

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: 0
Accepted
time: 11ms
memory: 2176kb

input:

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

output:

2.623671

result:

ok answer is 2.6237000000

Test #21:

score: 0
Accepted
time: 11ms
memory: 2180kb

input:

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

output:

0.000829

result:

ok answer is 0.0008000000

Test #22:

score: 0
Accepted
time: 11ms
memory: 2184kb

input:

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

output:

0.000284

result:

ok answer is 0.0003000000

Test #23:

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

input:

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

output:

Forever

result:

ok OK, forever!

Subtask #5:

score: 20
Accepted

Test #24:

score: 20
Accepted
time: 12ms
memory: 2180kb

input:

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

output:

0.002440

result:

ok answer is 0.0024000000

Test #25:

score: 0
Accepted
time: 12ms
memory: 2176kb

input:

2000 500
882856800 -46656
866607093 -1000000
481381898 64000000
-488180557 481890304
-783185249 -466...

output:

0.005573

result:

ok answer is 0.0056000000

Test #26:

score: 0
Accepted
time: 13ms
memory: 2164kb

input:

2000 1200
882856800 -2000376
866607093 -344472101
481381898 97336
-488180557 278445077
-783185249 -1...

output:

0.033021

result:

ok answer is 0.0330000000

Test #27:

score: 0
Accepted
time: 12ms
memory: 2172kb

input:

2000 900
882856800 -1
866607093 -40
481381898 2
-488180557 2
-783185249 -1
-816111307 -70227
9924839...

output:

313683.666667

result:

ok answer is 313683.6667000000

Test #28:

score: 0
Accepted
time: 8ms
memory: 2176kb

input:

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

output:

45162.555556

result:

ok answer is 45162.5555000000

Test #29:

score: 0
Accepted
time: 8ms
memory: 2180kb

input:

2000 400
882856800 -8
866607093 -99
481381898 1
-488180557 55
-783185249 -2
-816111307 -174
99248396...

output:

2145.965517

result:

ok answer is 2145.9655000000

Test #30:

score: 0
Accepted
time: 8ms
memory: 2180kb

input:

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

output:

3.414934

result:

ok answer is 3.4149000000

Test #31:

score: 0
Accepted
time: 5ms
memory: 2116kb

input:

2000 975
784172079 808971860
81381899 71917076
-712636352 -738530531
-622770179 -58502471
119667134 ...

output:

Forever

result:

ok OK, forever!

Subtask #6:

score: 20
Accepted

Test #32:

score: 20
Accepted
time: 415ms
memory: 5748kb

input:

99991 66666
-678240367 702595369
-125056128 663054848
574742591 -405224
-82244469 -11697083
55763190...

output:

0.001274

result:

ok answer is 0.0013000000

Test #33:

score: 0
Accepted
time: 389ms
memory: 6128kb

input:

99992 45678
-505891895 4096
409303335 -387420489
800445369 -387420489
324934094 531441
-800995856 75...

output:

0.000926

result:

ok answer is 0.0009000000

Test #34:

score: 0
Accepted
time: 513ms
memory: 6312kb

input:

99993 32768
972961680 -512
-622461107 -512
-65245375 387420489
-652933487 40353607
919122483 -134217...

output:

0.000882

result:

ok answer is 0.0009000000

Test #35:

score: 0
Accepted
time: 348ms
memory: 6480kb

input:

99994 20102
-740844274 -2048
489732031 177147
964768051 1
-652641626 -48828125
-21363456 -48828125
8...

output:

0.000171

result:

ok answer is 0.0002000000

Test #36:

score: 0
Accepted
time: 327ms
memory: 6132kb

input:

99995 45454
-410995107 39
894702367 13
-426401694 -77
800430197 -1
-295413329 -9
708661134 -4
415710...

output:

6448.500000

result:

ok answer is 6448.5000000000

Test #37:

score: 0
Accepted
time: 342ms
memory: 6264kb

input:

99996 35555
-14445778 13
-451475811 -3
444048318 -13004
422621424 -1
742439995 -2
723182696 -7
68727...

output:

1573.333333

result:

ok answer is 1573.3333000000

Test #38:

score: 0
Accepted
time: 332ms
memory: 6424kb

input:

99997 25600
-730866353 10
-218920426 -2
64717974 -1
137126596 -5
46821900 10155
745056512 17285
-964...

output:

119.081218

result:

ok answer is 119.0812000000

Test #39:

score: 0
Accepted
time: 318ms
memory: 6544kb

input:

99998 15263
-467407842 -1
-422165068 -2
915790698 -332
354357273 2
387305689 1714
-445403298 704
-83...

output:

1.488829

result:

ok answer is 1.4888000000

Test #40:

score: 0
Accepted
time: 315ms
memory: 6704kb

input:

99999 4999
-845589366 -183
771287727 -36
409548298 7543
-261071768 52
-182275548 3385
-137396908 121...

output:

0.000984

result:

ok answer is 0.0010000000

Test #41:

score: 0
Accepted
time: 442ms
memory: 6116kb

input:

100000 48364
979472386 980717496
207916820 208951865
-236221008 -237374910
348596303 348678721
70817...

output:

Forever

result:

ok OK, forever!

Extra Test:

score: 0
Extra Test Passed