CSES - KILO 2017 4/5

CSES - KILO 2017 4/5 - Results

Submission details
Task:	Uolevi and Market
Sender:	AVL-tiimi
Submission time:	2017-09-26 18:42:09 +0300
Language:	C++
Status:	READY
Result:	TIME LIMIT EXCEEDED

Test results
test	verdict	time
#1	ACCEPTED	0.04 s	details
#2	ACCEPTED	0.04 s	details
#3	ACCEPTED	0.32 s	details
#4	ACCEPTED	0.25 s	details
#5	ACCEPTED	0.42 s	details
#6	ACCEPTED	0.34 s	details
#7	ACCEPTED	0.34 s	details
#8	TIME LIMIT EXCEEDED	--	details
#9	TIME LIMIT EXCEEDED	--	details
#10	TIME LIMIT EXCEEDED	--	details
#11	TIME LIMIT EXCEEDED	--	details
#12	TIME LIMIT EXCEEDED	--	details
#13	TIME LIMIT EXCEEDED	--	details
#14	TIME LIMIT EXCEEDED	--	details
#15	TIME LIMIT EXCEEDED	--	details
#16	TIME LIMIT EXCEEDED	--	details
#17	TIME LIMIT EXCEEDED	--	details
#18	TIME LIMIT EXCEEDED	--	details
#19	TIME LIMIT EXCEEDED	--	details
#20	TIME LIMIT EXCEEDED	--	details
#21	TIME LIMIT EXCEEDED	--	details
#22	TIME LIMIT EXCEEDED	--	details
#23	TIME LIMIT EXCEEDED	--	details
#24	TIME LIMIT EXCEEDED	--	details
#25	TIME LIMIT EXCEEDED	--	details
#26	TIME LIMIT EXCEEDED	--	details
#27	TIME LIMIT EXCEEDED	--	details
#28	TIME LIMIT EXCEEDED	--	details
#29	TIME LIMIT EXCEEDED	--	details
#30	TIME LIMIT EXCEEDED	--	details
#31	TIME LIMIT EXCEEDED	--	details
#32	TIME LIMIT EXCEEDED	--	details
#33	TIME LIMIT EXCEEDED	--	details
#34	TIME LIMIT EXCEEDED	--	details
#35	TIME LIMIT EXCEEDED	--	details
#36	TIME LIMIT EXCEEDED	--	details
#37	TIME LIMIT EXCEEDED	--	details
#38	TIME LIMIT EXCEEDED	--	details
#39	TIME LIMIT EXCEEDED	--	details
#40	TIME LIMIT EXCEEDED	--	details
#41	TIME LIMIT EXCEEDED	--	details
#42	TIME LIMIT EXCEEDED	--	details
#43	TIME LIMIT EXCEEDED	--	details
#44	TIME LIMIT EXCEEDED	--	details
#45	TIME LIMIT EXCEEDED	--	details
#46	TIME LIMIT EXCEEDED	--	details
#47	TIME LIMIT EXCEEDED	--	details
#48	TIME LIMIT EXCEEDED	--	details
#49	TIME LIMIT EXCEEDED	--	details
#50	TIME LIMIT EXCEEDED	--	details
#51	TIME LIMIT EXCEEDED	--	details
#52	TIME LIMIT EXCEEDED	--	details
#53	ACCEPTED	0.10 s	details
#54	ACCEPTED	0.14 s	details
#55	ACCEPTED	0.14 s	details
#56	ACCEPTED	0.20 s	details
#57	ACCEPTED	0.20 s	details
#58	ACCEPTED	0.22 s	details
#59	ACCEPTED	0.20 s	details
#60	ACCEPTED	0.24 s	details
#61	ACCEPTED	0.21 s	details
#62	ACCEPTED	0.25 s	details
#63	ACCEPTED	0.18 s	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:30:10: warning: unused variable 'f' [-Wunused-variable]
     bool f = 0;
          ^

Code

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define F first
#define S second
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long n, k;
  cin >> n >> k;
  long t[n];
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
  }
  sort(t, t+n);
  map<long, long> p, p2;
  p[0] = 1;
  long lim = 1e18;
  for (int i = 0; i < n; ++i) {
    if (t[i] >= lim) break;
    p2.clear();
    for (auto it = p.begin(); it != p.end(); it++) {
      pair<long, long> q = *it;
      if (q.F+t[i] >= lim) break;
      p2[q.F+t[i]] += p[q.F];
    }
    for (pair<long, long> q : p2) p[q.F] += q.S;
    long sum = 0;
    bool f = 0;
    for (auto it = p.begin(); it != p.end(); it++) {
      pair<long, long> q = *it;
      sum += q.S;
      if (sum > k) {
        lim = q.F;
        break;
      }
    }
    while (p.size() && p.rbegin()->F >= lim) p.erase(--p.end()); 
  }
  cout << lim << 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: TIME LIMIT EXCEEDED

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

correct output
`100448091` view save

user output
(empty)

Test 9

Verdict: TIME LIMIT EXCEEDED

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

correct output
`100439561` view save

user output
(empty)

Test 10

Verdict: TIME LIMIT EXCEEDED

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

correct output
`100435546` view save

user output
(empty)

Test 11

Verdict: TIME LIMIT EXCEEDED

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

correct output
`100441107` view save

user output
(empty)

Test 12

Verdict: TIME LIMIT EXCEEDED

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

correct output
`100450517` view save

user output
(empty)

Test 13

Verdict: TIME LIMIT EXCEEDED

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

correct output
`67278906` view save

user output
(empty)

Test 14

Verdict: TIME LIMIT EXCEEDED

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

correct output
`67288062` view save

user output
(empty)

Test 15

Verdict: TIME LIMIT EXCEEDED

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

correct output
`67289186` view save

user output
(empty)

Test 16

Verdict: TIME LIMIT EXCEEDED

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

correct output
`67277799` view save

user output
(empty)

Test 17

Verdict: TIME LIMIT EXCEEDED

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

correct output
`67292946` view save

user output
(empty)

Test 18

Verdict: TIME LIMIT EXCEEDED

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

correct output
`59893004` view save

user output
(empty)

Test 19

Verdict: TIME LIMIT EXCEEDED

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

correct output
`58898150` view save

user output
(empty)

Test 20

Verdict: TIME LIMIT EXCEEDED

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

correct output
`131136907` view save

user output
(empty)

Test 21

Verdict: TIME LIMIT EXCEEDED

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

correct output
`120528479` view save

user output
(empty)

Test 22

Verdict: TIME LIMIT EXCEEDED

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

correct output
`84360885` view save

user output
(empty)

Test 23

Verdict: TIME LIMIT EXCEEDED

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

correct output
`265227849` view save

user output
(empty)

Test 24

Verdict: TIME LIMIT EXCEEDED

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

correct output
`290583555` view save

user output
(empty)

Test 25

Verdict: TIME LIMIT EXCEEDED

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

correct output
`259448394` view save

user output
(empty)

Test 26

Verdict: TIME LIMIT EXCEEDED

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

correct output
`298797537` view save

user output
(empty)

Test 27

Verdict: TIME LIMIT EXCEEDED

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

correct output
`257886720` view save

user output
(empty)

Test 28

Verdict: TIME LIMIT EXCEEDED

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

correct output
`261238357` view save

user output
(empty)

Test 29

Verdict: TIME LIMIT EXCEEDED

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

correct output
`223349203` view save

user output
(empty)

Test 30

Verdict: TIME LIMIT EXCEEDED

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

correct output
`222688987` view save

user output
(empty)

Test 31

Verdict: TIME LIMIT EXCEEDED

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

correct output
`227876438` view save

user output
(empty)

Test 32

Verdict: TIME LIMIT EXCEEDED

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

correct output
`234405809` view save

user output
(empty)

Test 33

Verdict: TIME LIMIT EXCEEDED

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

correct output
`178928274` view save

user output
(empty)

Test 34

Verdict: TIME LIMIT EXCEEDED

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

correct output
`186022493` view save

user output
(empty)

Test 35

Verdict: TIME LIMIT EXCEEDED

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

correct output
`215438196` view save

user output
(empty)

Test 36

Verdict: TIME LIMIT EXCEEDED

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

correct output
`178731024` view save

user output
(empty)

Test 37

Verdict: TIME LIMIT EXCEEDED

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

correct output
`194634751` view save

user output
(empty)

Test 38

Verdict: TIME LIMIT EXCEEDED

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

correct output
`5721937` view save

user output
(empty)

Test 39

Verdict: TIME LIMIT EXCEEDED

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

correct output
`6098943` view save

user output
(empty)

Test 40

Verdict: TIME LIMIT EXCEEDED

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

correct output
`4474692` view save

user output
(empty)

Test 41

Verdict: TIME LIMIT EXCEEDED

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

correct output
`4231961` view save

user output
(empty)

Test 42

Verdict: TIME LIMIT EXCEEDED

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

correct output
`4628295` view save

user output
(empty)

Test 43

Verdict: TIME LIMIT EXCEEDED

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

correct output
`170077689` view save

user output
(empty)

Test 44

Verdict: TIME LIMIT EXCEEDED

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

correct output
`158038991` view save

user output
(empty)

Test 45

Verdict: TIME LIMIT EXCEEDED

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

correct output
`158550902` view save

user output
(empty)

Test 46

Verdict: TIME LIMIT EXCEEDED

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

correct output
`159567145` view save

user output
(empty)

Test 47

Verdict: TIME LIMIT EXCEEDED

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

correct output
`159902950` view save

user output
(empty)

Test 48

Verdict: TIME LIMIT EXCEEDED

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

correct output
`113524436` view save

user output
(empty)

Test 49

Verdict: TIME LIMIT EXCEEDED

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

correct output
`109879435` view save

user output
(empty)

Test 50

Verdict: TIME LIMIT EXCEEDED

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

correct output
`122498648` view save

user output
(empty)

Test 51

Verdict: TIME LIMIT EXCEEDED

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

correct output
`115613417` view save

user output
(empty)

Test 52

Verdict: TIME LIMIT EXCEEDED

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

correct output
`125841387` view save

user output
(empty)

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

Compiler report

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 (AVL-tiimi)