CSES - KILO 2017 4/5

CSES - KILO 2017 4/5 - Results

Submission details
Task:	Uolevi and Market
Sender:	liianvaikeitatehtäviä
Submission time:	2017-09-26 17:07:42 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.03 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.27 s	details
#4	ACCEPTED	0.34 s	details
#5	ACCEPTED	0.31 s	details
#6	ACCEPTED	0.27 s	details
#7	ACCEPTED	0.32 s	details
#8	ACCEPTED	0.27 s	details
#9	ACCEPTED	0.27 s	details
#10	ACCEPTED	0.29 s	details
#11	ACCEPTED	0.29 s	details
#12	ACCEPTED	0.29 s	details
#13	ACCEPTED	0.28 s	details
#14	ACCEPTED	0.28 s	details
#15	ACCEPTED	0.28 s	details
#16	ACCEPTED	0.29 s	details
#17	ACCEPTED	0.27 s	details
#18	ACCEPTED	0.26 s	details
#19	ACCEPTED	0.25 s	details
#20	ACCEPTED	0.25 s	details
#21	ACCEPTED	0.26 s	details
#22	ACCEPTED	0.26 s	details
#23	ACCEPTED	0.27 s	details
#24	ACCEPTED	0.29 s	details
#25	ACCEPTED	0.25 s	details
#26	ACCEPTED	0.25 s	details
#27	ACCEPTED	0.29 s	details
#28	ACCEPTED	0.27 s	details
#29	ACCEPTED	0.26 s	details
#30	ACCEPTED	0.24 s	details
#31	ACCEPTED	0.25 s	details
#32	ACCEPTED	0.28 s	details
#33	ACCEPTED	0.30 s	details
#34	ACCEPTED	0.24 s	details
#35	ACCEPTED	0.31 s	details
#36	ACCEPTED	0.31 s	details
#37	ACCEPTED	0.28 s	details
#38	ACCEPTED	0.26 s	details
#39	ACCEPTED	0.28 s	details
#40	ACCEPTED	0.24 s	details
#41	ACCEPTED	0.25 s	details
#42	ACCEPTED	0.28 s	details
#43	ACCEPTED	0.25 s	details
#44	ACCEPTED	0.25 s	details
#45	ACCEPTED	0.23 s	details
#46	ACCEPTED	0.27 s	details
#47	ACCEPTED	0.26 s	details
#48	ACCEPTED	0.24 s	details
#49	ACCEPTED	0.24 s	details
#50	ACCEPTED	0.29 s	details
#51	ACCEPTED	0.25 s	details
#52	ACCEPTED	0.28 s	details
#53	ACCEPTED	0.23 s	details
#54	ACCEPTED	0.28 s	details
#55	ACCEPTED	0.32 s	details
#56	ACCEPTED	0.26 s	details
#57	ACCEPTED	0.28 s	details
#58	ACCEPTED	0.29 s	details
#59	ACCEPTED	0.28 s	details
#60	ACCEPTED	0.27 s	details
#61	ACCEPTED	0.28 s	details
#62	ACCEPTED	0.28 s	details
#63	ACCEPTED	0.27 s	details

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll t[1010101];
ll n,k;
ll f(int x, ll lim, ll & tot) {
	if(tot >= k) return 0;
	for(int i = 0; i < x; ++i) {
		if(tot > k) break;
		if(t[i] <= lim) f(i, lim-t[i], ++tot);
		else break;
	}
	return 0;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i = 0; i < n; ++i) {
		cin>>t[i];
	}
	sort(t, t+n);
	ll lo = 1;
	ll hi = 1e14;
	ll best = 1e14;
	while(lo <= hi) {
		ll mid = (lo+hi)/2;
		ll tot = 0;
		for(int i = 0; i < n; ++i) {
			if(t[i] <= mid) f(i, mid-t[i], ++tot);
			else break;
			if(tot > k) break;
		}
		if(tot >= k) {
			best = mid;
			hi = mid-1;
		}
		else {
			lo = mid+1;
		}
	}
	cout<<best<<endl;

}

Test details

Test 1

Verdict: ACCEPTED

input
`5 30 4 2 1 16 8` view save

correct output
`30` view save

user output
`30` view save

Test 2

Verdict: ACCEPTED

input
`4 5 1 1 2 2` view save

correct output
`2` view save

user output
`2` view save

Test 3

Verdict: ACCEPTED

input
`200000 1000000 35914537 42647291 87909684 169...` view save

correct output
`40048` view save

user output
`40048` view save

Test 4

Verdict: ACCEPTED

input
`200000 999997 61014077 43650830 20341927 512...` view save

correct output
`26287` view save

user output
`26287` view save

Test 5

Verdict: ACCEPTED

input
`200000 999994 70240264 96093067 55381233 200...` view save

correct output
`47716` view save

user output
`47716` view save

Test 6

Verdict: ACCEPTED

input
`200000 1000000 35649442 14455142 42097661 264...` view save

correct output
`37463` view save

user output
`37463` view save

Test 7

Verdict: ACCEPTED

input
`200000 999999 13117573 51346250 57165442 573...` view save

correct output
`48524` view save

user output
`48524` view save

Test 8

Verdict: ACCEPTED

input
`200000 1000000 74133476 67906882 94159121 910...` view save

correct output
`100448091` view save

user output
`100448091` view save

Test 9

Verdict: ACCEPTED

input
`200000 999995 93614670 59747155 91096808 981...` view save

correct output
`100439561` view save

user output
`100439561` view save

Test 10

Verdict: ACCEPTED

input
`200000 999995 77940809 63268835 58552239 837...` view save

correct output
`100435546` view save

user output
`100435546` view save

Test 11

Verdict: ACCEPTED

input
`200000 999999 93402872 57557618 74759064 708...` view save

correct output
`100441107` view save

user output
`100441107` view save

Test 12

Verdict: ACCEPTED

input
`200000 999991 83612399 82124316 69515438 975...` view save

correct output
`100450517` view save

user output
`100450517` view save

Test 13

Verdict: ACCEPTED

input
`200000 999999 53962426 90332194 89669526 527...` view save

correct output
`67278906` view save

user output
`67278906` view save

Test 14

Verdict: ACCEPTED

input
`200000 999994 78077015 71621402 94228781 627...` view save

correct output
`67288062` view save

user output
`67288062` view save

Test 15

Verdict: ACCEPTED

input
`200000 999998 61448236 93649865 83826482 685...` view save

correct output
`67289186` view save

user output
`67289186` view save

Test 16

Verdict: ACCEPTED

input
`200000 999998 42674581 80397818 85436433 525...` view save

correct output
`67277799` view save

user output
`67277799` view save

Test 17

Verdict: ACCEPTED

input
`200000 999992 87054268 82500803 58062748 907...` view save

correct output
`67292946` view save

user output
`67292946` view save

Test 18

Verdict: ACCEPTED

input
`118 999990 24606314 26881915 83697723 314...` view save

correct output
`59893004` view save

user output
`59893004` view save

Test 19

Verdict: ACCEPTED

input
`114 999990 7508556 44887712 13807527 1373...` view save

correct output
`58898150` view save

user output
`58898150` view save

Test 20

Verdict: ACCEPTED

input
`60 999999 70830090 54903764 84787294 592...` view save

correct output
`131136907` view save

user output
`131136907` view save

Test 21

Verdict: ACCEPTED

input
`60 999995 26547370 1696909 47532807 4204...` view save

correct output
`120528479` view save

user output
`120528479` view save

Test 22

Verdict: ACCEPTED

input
`82 999991 30344020 85572550 14839656 688...` view save

correct output
`84360885` view save

user output
`84360885` view save

Test 23

Verdict: ACCEPTED

input
`115 999995 54759837 94799018 75148969 609...` view save

correct output
`265227849` view save

user output
`265227849` view save

Test 24

Verdict: ACCEPTED

input
`92 999998 83834052 81737375 96920614 974...` view save

correct output
`290583555` view save

user output
`290583555` view save

Test 25

Verdict: ACCEPTED

input
`118 999990 67250889 58936420 59051268 534...` view save

correct output
`259448394` view save

user output
`259448394` view save

Test 26

Verdict: ACCEPTED

input
`84 1000000 93928620 74036291 93350031 581...` view save

correct output
`298797537` view save

user output
`298797537` view save

Test 27

Verdict: ACCEPTED

input
`116 1000000 57328438 70122878 82388890 502...` view save

correct output
`257886720` view save

user output
`257886720` view save

Test 28

Verdict: ACCEPTED

input
`64 999994 66326096 74371473 35345424 605...` view save

correct output
`261238357` view save

user output
`261238357` view save

Test 29

Verdict: ACCEPTED

input
`101 999991 76537247 62075235 55562035 409...` view save

correct output
`223349203` view save

user output
`223349203` view save

Test 30

Verdict: ACCEPTED

input
`96 999992 54160104 62176925 57826972 657...` view save

correct output
`222688987` view save

user output
`222688987` view save

Test 31

Verdict: ACCEPTED

input
`93 999997 85439260 80904987 73271551 933...` view save

correct output
`227876438` view save

user output
`227876438` view save

Test 32

Verdict: ACCEPTED

input
`92 999995 77813962 94408431 56259996 683...` view save

correct output
`234405809` view save

user output
`234405809` view save

Test 33

Verdict: ACCEPTED

input
`112 999990 49974705 72633033 41677908 918...` view save

correct output
`178928274` view save

user output
`178928274` view save

Test 34

Verdict: ACCEPTED

input
`105 999992 76300298 77811005 27684325 765...` view save

correct output
`186022493` view save

user output
`186022493` view save

Test 35

Verdict: ACCEPTED

input
`71 999999 62693484 87177530 45066123 393...` view save

correct output
`215438196` view save

user output
`215438196` view save

Test 36

Verdict: ACCEPTED

input
`116 1000000 90037623 54173518 87617924 724...` view save

correct output
`178731024` view save

user output
`178731024` view save

Test 37

Verdict: ACCEPTED

input
`106 999998 36516564 42111213 44365846 869...` view save

correct output
`194634751` view save

user output
`194634751` view save

Test 38

Verdict: ACCEPTED

input
`840 999999 26237876 15602392 84690614 992...` view save

correct output
`5721937` view save

user output
`5721937` view save

Test 39

Verdict: ACCEPTED

input
`943 999993 56464921 36827489 64259440 549...` view save

correct output
`6098943` view save

user output
`6098943` view save

Test 40

Verdict: ACCEPTED

input
`1842 999999 22720484 18646774 73741679 151...` view save

correct output
`4474692` view save

user output
`4474692` view save

Test 41

Verdict: ACCEPTED

input
`1279 999994 94762285 14088940 1644295 8200...` view save

correct output
`4231961` view save

user output
`4231961` view save

Test 42

Verdict: ACCEPTED

input
`1697 999998 97851850 63055272 31579609 528...` view save

correct output
`4628295` view save

user output
`4628295` view save

Test 43

Verdict: ACCEPTED

input
`807 999994 92111097 66175026 65616513 950...` view save

correct output
`170077689` view save

user output
`170077689` view save

Test 44

Verdict: ACCEPTED

input
`1419 999994 50559319 94606341 98969606 999...` view save

correct output
`158038991` view save

user output
`158038991` view save

Test 45

Verdict: ACCEPTED

input
`1453 999998 53864345 60040214 63738530 676...` view save

correct output
`158550902` view save

user output
`158550902` view save

Test 46

Verdict: ACCEPTED

input
`1252 999999 90006245 55183477 96168215 564...` view save

correct output
`159567145` view save

user output
`159567145` view save

Test 47

Verdict: ACCEPTED

input
`1341 999990 87329698 93796250 60725827 954...` view save

correct output
`159902950` view save

user output
`159902950` view save

Test 48

Verdict: ACCEPTED

input
`1440 999997 97841217 83382136 35620107 810...` view save

correct output
`113524436` view save

user output
`113524436` view save

Test 49

Verdict: ACCEPTED

input
`1826 999991 54543844 47545004 40426026 510...` view save

correct output
`109879435` view save

user output
`109879435` view save

Test 50

Verdict: ACCEPTED

input
`887 1000000 34460498 71787503 33446890 636...` view save

correct output
`122498648` view save

user output
`122498648` view save

Test 51

Verdict: ACCEPTED

input
`1170 999990 85096647 86660620 49474653 542...` view save

correct output
`115613417` view save

user output
`115613417` view save

Test 52

Verdict: ACCEPTED

input
`835 999993 54480677 51249282 39409673 833...` view save

correct output
`125841387` view save

user output
`125841387` view save

Test 53

Verdict: ACCEPTED

input
`200000 999995 100000000 100000000 100000000 ...` view save

correct output
`200000000` view save

user output
`200000000` view save

Test 54

Verdict: ACCEPTED

input
`200000 999994 2761 2821 4103 1824 1499 2287 ...` view save

correct output
`1485` view save

user output
`1485` view save

Test 55

Verdict: ACCEPTED

input
`200000 1000000 2242 3461 1843 4422 3117 1682 ...` view save

correct output
`1484` view save

user output
`1484` view save

Test 56

Verdict: ACCEPTED

input
`200000 999996 1727 4798 1438 4369 2651 4268 ...` view save

correct output
`1497` view save

user output
`1497` view save

Test 57

Verdict: ACCEPTED

input
`200000 999990 3944 1053 4668 3351 3236 4781 ...` view save

correct output
`1496` view save

user output
`1496` view save

Test 58

Verdict: ACCEPTED

input
`200000 999996 1964 3445 3391 4307 2742 3853 ...` view save

correct output
`1523` view save

user output
`1523` view save

Test 59

Verdict: ACCEPTED

input
`200000 999993 3051 4465 4099 2105 2142 3553 ...` view save

correct output
`1493` view save

user output
`1493` view save

Test 60

Verdict: ACCEPTED

input
`200000 999990 2957 3354 3456 1009 4854 4747 ...` view save

correct output
`1543` view save

user output
`1543` view save

Test 61

Verdict: ACCEPTED

input
`200000 999998 1371 2549 3797 3247 3424 2800 ...` view save

correct output
`1506` view save

user output
`1506` view save

Test 62

Verdict: ACCEPTED

input
`200000 999992 4081 4463 3326 4078 3790 4232 ...` view save

correct output
`1544` view save

user output
`1544` view save

Test 63

Verdict: ACCEPTED

input
`200000 999994 2660 2489 2599 2268 2084 3274 ...` view save

correct output
`1484` view save

user output
`1484` view save

KILO 2017 4/5

Uolevi and Market

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Tasks

Submissions (liianvaikeitatehtäviä)