10163 - Storage Keepers

[cyfra]

Hi!

I am trying to solve this task, but still have WA.

Could anyone send any test cases...

I am doing a simple dynamic programming on two dimesional array...

Please help

Thanks in advance

[student]

Try to solve the problem using one-dimensional DP two times. First you calculate the maximal security of storages, then using the result calculate the minimal salary. This really works.

[chengouxuan]

in

3 3
2 3 4
4 5
1 1 1 1 1
0 0


out

2 6
1 4

[plamplam]

Some randomly generated input:

Code: Select all

53 5
783 48 798 524 712 

46 24
788 658 541 351 456 789 188 695 634 392 715 828 576 902 438 784 502 610 643 633 44 917 922 72 

58 18
15 662 481 921 189 385 36 180 191 9 739 318 442 699 442 228 161 56 

7 24
581 261 577 537 550 987 72 86 513 975 997 197 912 574 191 55 243 908 16 832 53 132 381 881 

56 15
157 10 600 40 141 20 45 976 396 7 753 317 749 825 914 

37 21
320 11 772 683 416 173 680 256 30 349 995 28 454 970 532 487 716 629 322 453 529 

16 20
826 567 118 157 739 445 696 379 273 234 324 311 286 176 494 551 878 651 920 537 

59 5
277 744 309 351 256 

68 30
609 996 435 161 355 908 608 391 276 24 428 13 423 401 628 201 504 185 963 9 406 383 860 489 283 800 539 961 52 57 

70 19
183 690 122 787 63 804 93 811 215 468 440 133 309 314 596 594 710 738 897 

83 18
334 22 763 90 429 38 420 923 663 925 317 566 651 648 195 394 584 756 

58 11
31 199 211 31 842 322 980 587 830 308 109 

11 3
303 802 323 

26 21
836 667 969 881 328 455 537 875 800 24 385 691 576 477 776 583 975 694 274 538 158 

51 1
119 

2 9
167 380 723 278 59 458 901 611 689 

96 1
709 

51 22
476 590 17 484 176 214 501 500 988 697 419 672 245 179 271 20 746 920 127 617 760 224 

52 25
834 866 242 896 863 799 97 370 550 331 82 356 449 21 413 961 234 354 421 834 65 956 257 321 697 

63 29
832 983 984 339 127 225 318 737 882 775 603 372 565 251 708 439 708 400 993 780 586 881 58 158 885 728 760 931 367 

21 15
598 440 982 98 658 523 24 108 515 145 255 100 174 636 608 

54 27
353 622 21 115 490 180 631 961 257 184 372 763 191 45 779 164 446 970 612 423 881 909 966 712 880 622 430 

79 29
816 407 302 457 236 796 78 548 504 82 918 83 160 999 340 337 934 128 520 685 103 225 825 111 177 474 469 384 111 

1 9
407 216 253 212 706 734 39 643 748 

75 29
905 85 248 64 415 635 434 30 913 470 688 169 789 369 609 90 36 631 412 346 410 322 914 502 761 391 527 19 706 

0 0

Code: Select all

52 2817
238 13774
94 6038
832 6492
97 5828
226 9563
369 7683
31 1937
163 13032
114 8811
94 8373
70 4279
114 1428
345 11715
2 119
723 1624
7 709
164 9679
192 12004
225 17032
212 5215
207 12707
130 11513
748 748
150 12566

I used dp to find Lmax and then used Lmax and another dp to find Ymin