All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
mostafa_angel
New poster
Posts: 23 Joined: Sun Oct 04, 2009 12:03 pm
Post
by mostafa_angel Fri Sep 23, 2011 11:06 pm
Hi...
I Get WA for this Problem...
I think this Problem in Maximum Sum in 2D array. so with problem Ranges (100) I use O(N^4)...
Can any body help why I get WA ?
This is my code :
Code: Select all
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define size 101
typedef long long int ll;
ll input[size][size];
//ll sinp[size][size];
int main()
{
int t , n , m;
ll money;
int cnt , tcnt;
ll sum , tsum;
scanf("%d", &t);
for(int pp = 0 ; pp < t ; pp++)
{
scanf("%d %d %lld" , &n , &m , &money);
for(int i= 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
scanf("%lld", &input[i][j]);
sum = tsum = 0;
cnt = tcnt = 0;
for(int i = 0 ; i < n; i++)
{
for(int j= 0 ; j < m ; j++)
{
tsum = 0;
for(int k = i ; k < n ; k++)
{
for(int l = j ; l < m ; l++)
{
tsum += input[k][l];
tcnt = (k -i + 1)*(l-j+1);
//cout << tsum << " " << cnt << " " << k << " " << l <<endl;
if(tsum <= money)
{
if(tcnt > cnt)
{
sum = tsum;
cnt = tcnt;
}
if(tcnt == cnt)
{
if(tsum < sum)
{
sum = tsum;
cnt = tcnt;
}
}
}
else
{
//cout << "Break at -> " << k << " " << l << endl;
break;
}
}
}
}
}
printf("Case #%d: %d %lld\n", pp + 1, cnt , sum);
}
return 0;
}
calicratis19
Learning poster
Posts: 76 Joined: Mon Jul 21, 2008 8:50 amLocation: SUST,SYLHET,BANGLADESH.
Contact:
Post
by calicratis19 Mon Oct 17, 2011 9:55 pm
How to solve this problem within time limit ? It is not possible to solve it with 100^4 . Any idea ? Thanks.
Heal The World
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 amLocation: San Jose, CA, USA
Post
by brianfry713 Thu Aug 29, 2013 10:45 pm
Input:
Code: Select all
50
7 10 4361099
372635 403776 757342 613647 255624 827769 988581 15911 261777 184255
78024 387910 348870 200215 585883 814196 380850 444434 610663 873209
210084 734511 355740 416582 27004 585921 880676 188471 270919 377865
549570 643554 781641 823264 257201 553617 167385 762134 85880 945514
946389 680257 333425 811611 396824 919308 625808 777674 363742 236471
167236 90178 487334 522976 506760 514339 108897 387437 219162 379816
765302 285084 23371 63296 624700 796924 133265 792085 559059 219146
20 1 158899402
587376
833412
296227
506684
459220
73901
386778
212043
241137
476956
699377
280466
983717
730068
389363
371154
465582
285532
652808
750666
16 17 283375365
622179 365722 683803 697590 101220 421403 719391 623 525131 69155 813202 548168 528375 403455 934946 256770 160945
411903 472499 441411 911972 718920 347126 799478 184502 632658 968638 935169 974265 201095 826887 112797 83169 510691
810387 184389 448446 46130 701364 973577 115285 514566 521745 160012 918021 456692 933134 595318 384947 405634 36729
813271 124554 383856 612749 309056 532866 581387 760577 23484 298834 587465 136281 382003 98156 463020 82744 62954
25503 784108 36531 140788 815026 558277 817153 249400 531321 750287 844718 432620 155921 881448 245891 796827 781656
374992 622236 314522 956379 382813 854358 771566 486630 990639 153569 101138 970012 236314 164092 995515 536774 200624
652655 351801 275253 469808 601201 322926 736448 445919 755546 408721 843719 517789 205549 625375 892781 827785 456250
849160 726950 310608 620726 213581 817600 290648 314719 787612 43314 478812 299479 580088 195788 952134 448241 471041
938295 49442 793967 674743 11714 65865 83464 855433 583654 289013 997161 476435 633150 453411 841947 360101 280371
979026 90034 97971 269674 404753 401935 829340 399917 701414 409428 595705 653549 374022 583098 108196 423464 377065
782939 951530 442930 866403 323316 542936 671769 320477 19371 821271 290240 861319 697724 570611 840345 787758 184935
626371 708864 586870 455711 108781 804637 381491 704487 974538 271865 803937 82734 695330 181003 865673 163212 140285
248428 486528 683222 920197 323357 218945 257821 613597 80264 955545 700561 436961 259656 401848 579684 968520 505070
551747 593653 309707 449591 814492 284245 721456 618430 366979 933138 315785 749004 96351 456070 997433 99231 655644
433982 422589 874590 691803 552538 471206 163701 769451 424520 939709 171299 4204 424581 192722 72304 18234 502429
521895 349079 303027 243351 967509 186358 692842 283294 935363 789193 255716 932796 404776 427713 366778 827365 818655
15 17 370289860
254987 182059 714381 194696 869711 234938 619277 62433 307242 153863 81214 829137 502942 384241 588840 470451 570600
281682 270097 22315 587227 42166 955111 992004 469879 838241 335721 288534 929527 748329 94747 184514 930389 325481
895562 800100 560419 514839 378885 384013 185055 460099 729502 687997 360693 318342 674801 931293 116377 944898 469960
219956 987064 425071 728312 973295 779664 580386 778181 225544 328715 872929 410058 775456 198410 821973 91908 275181
336812 470793 659194 38219 930893 905048 726217 807938 739742 401018 255583 856119 862268 725543 592428 365685 666966
320740 338980 446630 417478 117162 672174 746194 506443 598585 38002 221205 420558 129911 12738 273722 117056 188284
311942 564301 93332 554511 372239 833074 955529 627822 205546 817797 353365 797974 183482 20331 635066 38815 983314
52545 672329 171840 315091 695124 770425 869445 916329 707335 515708 445419 497410 632765 633703 325704 197066 727035
880215 569306 76461 352096 713480 282007 686245 66846 596333 386080 603529 747752 424895 586843 316649 613576 758684
148092 308700 45461 17537 225029 269149 533246 670448 282911 166011 820503 608615 879429 547538 5182 965087 140351
873630 678568 422359 559875 261766 535044 945955 865295 799148 887202 968491 115797 500778 727175 263889 809478 288988
281427 550859 74489 331025 737659 357400 497036 558162 482367 376465 622052 487549 341553 762404 361179 536473 701115
921055 798239 752511 383362 663534 551660 270565 148377 667457 771343 391904 931347 580822 680893 729126 131681 755382
60151 869341 629135 73539 943855 111502 966356 565908 115404 824261 328312 476583 360734 545779 913990 158973 298290
813705 338860 849950 84270 487237 517408 371965 879142 965107 469139 76387 210585 117173 348121 270736 502866 977256
8 2 391605111
826983 12629
720515 651245
857293 197098
11979 403072
627441 687305
701363 441146
542517 67665
41768 546106
14 14 892425247
66532 882873 17987 277117 46 366109 64205 502912 859717 924832 465985 464828 268168 478615
701695 919413 852260 898794 447744 255333 42587 135049 473048 85 193918 540713 41853 740025
642139 971938 681625 708671 854811 699613 502141 371209 582074 82698 390473 958143 523883 856459
422972 792051 851426 641019 227816 703686 539813 675560 475371 98752 326962 948419 98837 520880
5485 657042 777257 647624 628981 458883 872647 144 674848 891140 371354 256922 973839 278179
215065 497722 134638 154389 806125 502416 311761 33941 206103 851574 225853 681474 466679 552815
629894 565516 590048 151731 222559 883657 799355 367892 342540 672002 368036 533740 79495 739390
790662 53334 533922 522080 67408 184912 192821 873533 687329 504582 423826 893432 872509 649679
574906 855540 718847 721152 937408 825247 872883 676319 708904 188590 44211 567797 376945 412248
101537 456440 667990 408552 509774 201912 446984 577182 386825 156157 967067 74154 177092 390893
483938 565953 556924 575196 421493 275771 296349 875253 101018 685584 551573 326275 390527 595784
894072 767472 524384 511961 223912 192375 436865 250038 394287 400201 343572 297464 556359 826991
887970 249803 217884 371908 815756 291160 947105 753601 566932 759806 628854 184302 961742 696779
510577 352269 292564 921001 636093 816948 949315 376357 525675 902532 142747 436315 302734 486319
20 14 188829662
621750 625248 563898 510010 957356 855059 457115 227309 421991 733273 856163 122645 695016 552943
633223 563637 361859 70576 199731 695159 536243 92440 220835 438776 235188 657150 741510 237859
907281 116955 67522 45383 742203 631420 555394 215911 486479 528861 443220 908470 262135 299383
547468 473503 368678 180691 553492 246889 767619 269575 942049 820215 362016 679236 258991 597204
336386 501 835063 243667 633808 902585 805403 892363 534006 360797 108274 536837 406010 551494
445308 184497 367229 992776 658000 252260 689819 727845 499149 973790 997420 957550 794005 359436
636786 569348 472992 973172 569849 308056 733192 720009 726993 54947 612372 777351 415744 720646
314189 338106 272140 275849 522604 639370 268625 696956 891630 474796 424801 907131 964938 422222
864682 275296 298010 501468 844644 771003 990993 930846 595411 240537 650855 322404 295484 779580
616108 227580 500226 930297 82038 288719 206146 604642 444441 991123 301599 852423 982271 242752
759554 947209 181326 140588 222505 479337 158409 583502 766692 149402 514348 878455 906291 165203
717211 718127 461135 333319 462059 961362 263616 544097 766433 469762 665092 210874 460885 966691
63297 443156 725795 339203 906718 907122 479792 129223 902811 638201 712725 669503 303955 743425
547958 210246 424981 781521 444725 886116 114841 423136 847478 378457 967233 613911 848220 632325
341137 825457 115368 920786 268614 357516 259990 175332 264638 739782 820907 167449 894335 49985
353304 198290 793410 417614 924888 734743 199135 885965 620860 313976 309101 984690 692434 792686
114954 57006 941364 456091 882463 573084 376878 667429 930600 636868 359113 195238 893002 180021
362687 303689 746358 232343 501979 56120 649957 943219 790864 849093 829184 411724 163069 654637
396414 855503 447323 27720 428861 388687 483812 311325 478124 377042 495106 408724 530262 854220
603963 939616 550593 483002 243305 296951 715346 261636 353071 365303 204855 143935 214396 550391
12 19 735721380
984778 265673 685055 12498 694535 590095 12662 522212 68219 389704 17318 476943 436318 387890 597258 375934 938483 80261 135591
751786 311959 397227 104858 193614 118434 765145 924363 185177 353509 818181 906557 338287 83854 591613 867137 294741 181708 879800
816953 766279 785856 350624 243222 738527 738514 840481 630813 676998 437094 766405 945136 265405 163632 49994 459019 798419 331492
383382 499948 201353 717915 922858 539640 801770 514471 923129 96511 212531 319281 429817 495162 621490 780441 738384 360017 518955
95217 990830 712305 48663 757235 657442 314068 437220 223788 773088 751991 71632 672822 251939 272985 390738 174797 328977 708860
205620 252107 321723 934503 87740 751540 429665 709230 531981 684402 69247 567289 779619 576430 795946 828283 333665 969740 658703
287237 709881 948143 39228 781513 620966 807520 570851 528056 982317 416180 236916 704290 184639 558639 638793 272380 826532 584811
981610 358513 269213 567210 442154 565184 143640 754453 909819 993657 240545 568523 280895 950426 33018 836475 248292 653984 643995
335495 698392 142665 751675 451660 846955 936315 526652 2100 208695 353184 586911 706657 228049 372476 273867 670204 937661 933859
941009 363832 927517 181554 932355 724764 648333 965374 561239 896625 135710 721587 232120 350455 380604 500147 802115 743911 436462
328767 746011 161509 681951 849275 384519 910001 738103 174738 96557 675764 108598 553918 555949 552467 735472 488304 277231 900157
970030 838470 796782 622093 76409 545254 972548 457013 561754 774663 200924 514568 619783 463288 676078 301734 828915 576949 728087
19 8 432340996
759135 376637 894914 315084 929104 146739 319740 206335
46896 806123 561158 360031 944568 637567 905285 917116
610933 983391 208131 328209 497960 344266 307849 690390
646001 136764 267339 890440 220135 535378 231437 495622
912016 126351 327058 841120 789442 646798 563808 836339
969273 124966 196370 913841 278885 618007 347309 406170
601399 555441 734380 99359 899707 558581 306101 62060
211698 573440 468853 431833 625170 700290 443807 537186
342993 770865 894659 132436 417663 458467 968775 903289
99785 681497 817130 378670 299504 164440 784841 417255
236233 35573 32966 652292 594154 339067 714353 805852
428859 183206 754037 54030 399848 197844 591216 259193
968709 485875 391629 902725 460694 876756 806014 560479
74605 139496 455502 374110 303936 240343 791365 56521
792268 340684 708814 386422 679751 939519 192275 108611
122725 462664 162641 38925 660509 270209 298118 629218
272437 206100 531943 733131 82856 854309 809963 673814
993806 265465 47924 814094 22160 355641 386968 814428
696325 95782 200850 892429 35301 909477 1040 674378
3 14 521713302
549003 950242 527773 178221 739031 733873 226517 472163 333082 80826 798478 6896 590984 580295
571172 921431 602455 926813 308399 416883 139491 404181 134085 548272 955834 559915 65664 146564
448409 745697 859867 997412 212291 387640 175633 951323 121514 918502 939838 970948 515681 738316
5 18 847318610
549016 544448 437418 992181 369199 854301 131672 773380 504738 196296 245566 581005 261960 392130 29414 7657 768349 26826
219949 672342 718812 687624 310208 637314 627462 281156 669347 882130 259000 292365 717093 808016 836813 154511 800197 206013
525164 448222 495745 546254 644518 257664 127260 422831 166146 156674 430488 934496 699853 166789 606838 418665 370765 917046
572331 998227 714554 241679 396709 973554 50396 630154 297922 887209 784665 614471 609574 826181 62693 621672 888788 223564
879336 16048 646395 45482 689074 593235 496330 388927 276377 619520 323944 647142 52918 896276 161722 767472 654307 558431
7 4 41188584
555300 108264 489603 169772
717839 832137 748817 855863
720925 488733 251551 253325
651480 813385 942399 244716
309716 331327 521093 929236
655271 684587 982155 67899
846309 265979 722206 921093
19 2 402626031
78658 51526
631986 248430
285717 464123
513600 141580
701400 2333
393131 954725
653814 722868
897125 898530
32584 744804
935975 478173
916427 620562
976680 500679
983224 242659
222885 904317
766017 682499
530348 361028
734025 162334
609458 536094
142810 123058
15 11 65641744
587157 798936 295558 826377 212413 710440 858962 473569 646415 853487 389996
783329 346519 890675 282905 589178 629913 703574 871548 312412 233922 232576
562789 912609 358386 98883 571771 997797 292909 415981 639541 396418 731269
451451 222795 460034 161891 598109 933603 324658 451596 839952 624339 798115
730627 907245 903646 876892 610819 291546 705656 361094 40474 268445 790055
915212 883680 361826 429361 176589 294159 68902 573007 541781 520353 312155
1815 198596 910264 451771 523254 878213 291723 147594 192680 538702 54839
96326 415595 665658 904224 121251 543104 944698 906049 333159 376263 789729
694985 805624 966319 989145 390879 55678 530926 427584 884185 49093 626181
794450 500864 149435 672663 308939 297029 381695 847642 351868 478022 779589
533879 898598 900840 593335 359649 806889 926495 735912 596619 621480 541536
79290 126977 448767 651320 174255 876352 51858 223349 502533 846308 240565
651968 35323 549505 465350 417018 913499 333570 411392 693088 867449 309991
110280 460785 185992 917170 903632 921904 30141 525112 979792 625783 168442
428560 793455 342697 821264 845313 82398 323797 207973 839316 492117 759648
2 8 52693019
818672 291038 104411 511760 674839 930754 138392 651976
116746 55562 555608 555002 602055 597073 534795 744190
16 8 468053998
624564 300971 899311 706963 624768 623637 546279 633237
383285 451452 590705 76304 270124 398095 697068 298236
72934 627822 436628 724911 260921 8543 280519 815923
126950 877592 867070 387493 159459 346777 441491 784024
647748 857154 7339 788868 480791 69970 422106 380429
37774 529163 456733 824250 927258 153801 122486 192
297976 75466 725103 558897 600361 521975 891172 727312
915919 758243 114805 591731 105020 72648 892107 269121
929802 899446 57989 410594 485768 996447 791023 523542
525610 764108 347792 452868 434262 986630 453061 732238
62096 694516 807487 662458 732843 215011 906122 648763
973254 537279 240494 594627 609927 132601 863748 539729
548399 438089 466675 34167 434537 774050 557709 960147
54511 421853 929368 488773 408483 382429 737363 470579
593297 544850 649389 326141 759861 71863 491256 249468
609142 248102 844095 219069 897055 224195 275151 961806
5 19 10995971
96821 548581 70034 573321 603092 8239 502689 91865 416722 401470 829228 403653 994767 890430 569395 837260 166643 641258 844868
416111 250401 92970 776558 985822 506377 753 777325 468183 663038 35504 980508 276211 100437 566894 849532 703529 575133 868573
311746 508207 270043 140974 911861 781163 547756 481256 134775 714399 122514 979644 646863 889267 588966 939773 875090 611696 940527
168767 79879 119917 720623 576740 396128 821060 143634 762013 524589 235120 630586 836335 259679 900630 493661 171540 681793 41417
169148 816568 272169 808015 312564 435384 697282 901531 375157 88724 513227 832036 257492 109458 951953 978115 686198 348082 799176
6 16 537840117
97657 740681 676453 357336 157663 686466 45229 839456 244236 214377 172377 516405 22392 484941 468141 236027
902824 843298 324751 932403 191687 582243 41862 143640 76711 244412 491722 392239 106949 118169 232356 204606
375203 425161 78295 532866 111628 123524 888675 355864 854253 61052 388621 392998 62345 373114 629025 481522
732764 953776 413925 924451 52372 972139 68092 645435 216552 76166 37674 323501 194336 270030 44460 85891
211544 639107 618757 323172 762631 23784 195388 133236 601188 100361 526234 663534 473475 155259 661408 206239
625388 75333 130691 194112 563825 715135 839547 780377 791301 877221 620230 501989 663603 181042 587880 875147
10 11 765198318
99132 746774 910059 748721 347963 10420 274955 527849 483895 946567 189257
206487 571955 780942 853530 766067 344767 568665 605614 641496 359966 999187
778079 378308 662790 959121 966188 537938 295623 205530 252609 911107 952305
162669 659828 816620 689441 934784 860821 689689 397703 566430 896176 969658
347372 266058 252077 208492 834723 374043 366340 711041 889582 660771 89349
552372 136245 571890 606662 431868 777420 375624 342975 246077 54645 519156
579049 744086 970292 439870 950127 367995 6300 846303 854005 870025 628713
106082 594869 463436 996477 961209 174478 886059 621981 780179 954783 758226
352069 77798 706446 645842 453422 565773 891919 508067 84929 470969 768505
55221 910839 718633 423216 433492 81288 277221 303517 710002 899655 898386
11 5 652375947
864268 298543 514280 160800 769679
788858 512869 847477 495304 158711
817251 61078 566983 841670 662359
37952 610175 717581 465143 845160
657149 898635 442801 934371 718504
669155 350378 616890 358945 762863
509190 739566 577758 23470 900366
347437 812329 413235 711266 307633
88299 528517 885063 655282 370187
547423 209586 496715 781356 191081
858227 438505 606069 301028 889228
14 4 57239605
457816 329129 518822 967006
585047 96580 506828 485413
960370 319157 415000 671636
143143 19651 200154 544558
674933 86693 91981 400871
583408 389689 591953 441636
828195 198022 742664 233775
38947 229200 989734 496763
74681 508556 980121 659728
121489 486950 661493 81859
806107 592845 753495 465602
612497 470001 10161 287430
556695 618494 688302 656455
8184 796607 614443 352731
10 1 48586504
33576
102660
92593
46692
693693
117501
26813
353421
238990
30115
7 2 739836222
124111 107049
818177 736608
577050 828338
540391 650097
446833 745045
822905 455017
541652 437348
1 14 740310808
426958 602561 413468 519551 649253 107161 637053 192419 976934 392395 222534 24552 745949 575109
5 19 907393287
885272 946400 221625 942015 112850 184810 687060 935755 639827 745064 373103 480279 797697 200264 907238 400259 130084 426789 565864
753598 580194 274635 730532 488942 13522 755085 234891 588631 420101 604241 981918 821725 66993 719896 763741 179843 904706 450801
115598 60886 195866 5054 541165 509915 721670 448403 426526 851754 391545 508743 605352 488091 783378 852237 493385 313252 123674
244628 901884 543775 365221 400154 365500 432215 636402 645593 612058 541109 96395 244009 118347 808613 765415 659512 834880 487085
624268 261407 338839 532165 286502 944192 536608 586232 796429 546346 899485 920103 790974 801369 980230 156196 717875 345730 588411
19 5 34716820
411739 604071 477182 530086 929036
242597 705950 280268 729682 846570
58027 584874 378735 344529 45418
431696 930762 841847 978042 830247
278302 285368 147968 774884 957916
865843 636966 62679 736473 628290
779501 148212 748713 256683 678298
194101 15633 384249 474370 745315
230819 532397 846541 125907 393279
891959 73955 840393 250158 568349
186992 44812 853717 334960 819696
327986 717155 456663 390665 969981
601305 686518 118193 350019 943202
312844 60472 958835 697093 51194
220502 444264 99944 583396 86523
493223 475355 160478 333616 725514
728827 36960 770326 98897 888272
590023 426883 121779 46686 817548
91760 647991 504067 209954 514362
2 19 230091186
438808 736243 658733 175662 696859 758677 759058 783383 768252 234414 460213 618220 476280 189041 655180 246606 804290 543452 352981
231173 665232 916019 565073 756992 80363 585492 483298 111077 549113 522448 202264 504273 258691 860998 679936 471903 136027 955346
7 1 402706112
715499
522500
182392
420892
694033
945351
741534
6 13 560489059
419069 730704 54133 176062 811067 155977 175712 922144 221443 698161 640761 725716 473204
18111 922004 461459 154138 393703 716745 574770 99815 948597 97271 282208 885841 307656
743911 143728 545141 42243 632787 964211 772947 203272 656625 100366 359250 348689 538863
580693 46850 179624 822761 36407 714087 261118 497866 384577 654821 730964 959348 270988
195913 572971 553196 598106 880627 813459 741834 425768 855703 374622 906331 145002 94246
79308 761721 453496 427998 300584 550541 991200 996560 889655 27607 710647 150773 41826
5 7 424289141
54572 592934 1407 627543 662483 599513 24522
475942 857700 450291 847997 232322 872974 509352
842920 952283 271073 296417 380281 571657 363310
371481 568217 252965 915441 795216 920090 473619
890440 242036 279113 461365 351323 280520 605260
7 6 402629782
489748 254085 596426 337746 2759 469400
847098 845680 938035 634523 142097 318316
206180 21759 206150 290749 791077 637943
602317 711167 627914 9109 469556 907027
470474 820879 187547 592087 834685 583932
738222 324433 354370 334648 178531 357129
320400 541981 202809 258436 176504 861258
5 17 108883017
815606 706137 674095 453549 308454 385262 81463 317564 854818 504842 304390 675697 208741 896477 26734 792674 634699
867520 147044 485699 46051 20525 806100 104385 223335 580888 280889 84593 190344 179926 967611 5951 886063 158058
975852 710870 59673 573668 28434 430843 78510 332824 622893 287252 745654 649627 596278 896705 517147 259674 382405
79551 280199 704857 183936 503534 285745 464825 588128 992441 161103 72091 998392 563519 230150 974245 274389 806175
64265 819175 237018 142775 668351 859911 430027 414005 25891 26305 827063 59390 802331 209468 138941 82531 430677
18 6 274232774
304055 690545 225215 981510 278989 223608
545029 25491 714205 335770 831666 778470
154945 68684 437597 339649 444948 867625
753654 987191 410282 97069 46581 212614
822889 185523 811497 253566 24752 397562
486340 845159 604460 711556 826670 883449
451516 888051 908940 682073 740174 740606
976895 411471 325642 414492 751120 286942
798469 21127 274133 725104 118196 320715
454070 941086 22590 265567 711004 47342
663129 197345 892502 267589 425253 235524
667390 393121 639927 576330 75194 896453
316936 52089 307925 158931 982933 59045
445873 297755 596524 720007 22859 714721
557074 476929 172159 579664 742496 883163
627006 921977 596860 35860 705919 538465
787736 373309 931586 944016 949640 6780
840469 266576 575221 148394 941859 74507
13 14 57372261
320316 107740 395121 551389 181166 388402 239900 760830 130898 123064 904188 52875 236276 456401
758794 774742 244137 132104 222680 704505 81744 745813 544975 864672 837386 209721 806532 911893
449865 710617 284155 770182 334709 195628 837923 515875 584030 77824 276705 231280 717240 697245
800508 953516 153646 559302 244610 914136 207758 467291 618641 805854 213104 679968 186879 50490
889690 993411 478736 339555 220380 762891 626089 555089 474872 464013 70964 575254 541837 864021
806535 259077 561266 123395 728945 714913 682697 973556 145401 406808 957199 764042 212662 170303
444011 399541 737145 850053 909304 215881 189608 129684 495125 332050 684773 486349 796063 272089
61603 854252 136110 384490 629681 213729 507885 358626 444994 706935 848534 590395 113743 805733
870789 842757 492388 314800 242299 745886 681205 667955 961767 387166 313992 456892 719216 515117
943241 515279 787207 521197 885883 439669 422039 515564 169750 446277 390542 614744 153212 239077
205139 783307 561162 75929 626064 569903 907081 384715 315789 588287 52671 277556 975453 883015
250801 211021 398132 710394 726300 701691 747943 128535 657713 169983 644099 827463 616260 550993
442208 285824 790070 163699 69131 867585 755980 211547 437488 663062 596263 269629 767701 165286
18 7 348048300
830690 470527 962785 541085 713179 664477 805380
841714 322190 975363 2165 149653 107975 553158
108213 910151 859581 271913 979282 243518 27893
707182 197358 690955 303445 466987 975008 985083
530524 234514 33384 361215 221393 996169 418652
934572 176998 224032 292638 499188 715748 294803
165194 340075 364314 273407 250227 223895 545320
745861 467413 573214 453043 664771 780521 756488
648110 755530 257923 694986 506396 291307 56201
727790 803829 991205 178714 980827 215238 471353
996368 447338 282508 161562 787413 646822 951321
37640 387069 496642 783502 370834 586208 236545
551957 883081 509386 200067 638611 767309 895054
661360 574969 467607 905502 895150 458813 84216
392329 190403 71921 388697 637741 354430 66611
425154 517604 17933 979147 421026 30927 762649
791860 133487 515546 860170 16568 541284 60237
655180 824946 471643 832892 399915 455603 738394
6 9 611338961
203746 621171 927236 592444 775264 798018 175407 716770 315622
709692 695917 253000 256971 458566 561213 390458 490465 421383
407027 31749 997972 578559 856695 469616 411451 772962 441571
666197 584379 872339 521511 788126 493510 448747 896922 785126
246765 588681 501896 78740 298374 197814 331740 555345 172732
892953 945804 663197 830688 869183 211299 828661 447742 584346
10 6 979357308
256200 41742 458040 644891 79605 762518
138401 528353 659440 923527 291470 248122
941775 886562 62848 139589 734655 134545
312322 143960 596701 491871 974649 465884
703170 319662 913626 803869 134291 289171
677530 906843 847265 135570 551734 926871
898089 206487 971576 73881 646366 779398
322003 588141 665961 901203 727731 400616
35749 556405 544576 632450 48276 35577
98335 267799 355239 528313 71668 5882
6 19 666912725
664750 401120 464459 107973 299209 670946 79549 373091 833664 858948 211446 421806 41261 112650 149537 441877 148399 222294 502805
780849 270570 54735 395536 538369 409974 923850 126389 415857 257687 875587 844934 438789 276708 309394 546763 92269 496692 142664
981712 330357 517964 193159 752163 559225 822161 418052 517454 970560 640346 536612 267761 427268 591347 663298 481990 517673 103500
608379 449882 361187 319 294817 799976 793379 604211 346739 885648 617255 5756 383713 463964 523720 576872 732479 82946 399033
666883 600400 885945 823581 653364 670058 250850 244711 849708 732840 762385 953208 857571 728619 830747 857890 23436 630724 651269
143999 493815 53270 761255 499571 953335 741571 539644 46559 474051 622590 961944 140934 739342 847889 964516 909059 517947 731718
11 9 470464557
432507 837216 322129 161127 667964 696372 700915 815040 863993
844915 825207 433615 122522 841131 386950 864093 380775 433509
338144 519717 395453 995431 259059 243342 476299 168118 277642
208017 838241 161650 672575 787100 515218 511056 948227 699534
207428 649143 514574 587774 10410 339782 21389 132932 180913
408340 513377 78040 841849 851522 597757 237303 363305 373168
996997 839604 541287 790991 47621 895880 468993 236548 682980
984212 263956 147560 200098 471385 313055 714673 575511 839817
570807 596900 972749 268072 5240 486126 346112 363442 854000
943869 117097 733657 317037 630446 573261 374676 421438 137234
786908 406783 373782 986241 390995 637739 133801 107446 625476
9 20 905200986
803025 909278 314239 292126 693702 835832 778252 39814 199274 148605 500035 832723 882262 333424 463169 971876 224453 400959 109110 527713
807743 999245 513954 715090 636984 164107 822536 778812 127315 161007 496151 446692 586637 810390 738818 280339 162574 517071 836505 878200
182028 852892 710923 64290 186317 690445 552518 927122 607756 661629 454835 931851 177226 968790 646942 330562 132897 985830 109374 776565
663190 121877 223257 249827 448619 962076 46519 611194 995499 883024 489394 177527 735917 716670 758169 438586 407115 310688 882060 531223
488669 336895 463075 665895 822037 626369 996457 471287 612199 622183 247852 791741 744060 471109 557921 192679 949537 604440 320225 945036
487464 809620 638915 739733 42642 397085 694671 966109 224125 576731 497332 229146 429979 960407 411393 252016 586776 924202 723303 715328
62737 971155 507069 806797 958617 64990 515828 908154 669430 836054 369543 673247 162026 8458 929332 204668 921895 624004 170777 146020
200735 184461 891518 147066 144869 819263 399083 731645 743465 638738 446973 806202 609894 470395 129351 84863 535385 161532 509369 721168
513938 878912 394415 675964 887371 840099 396984 809266 464103 84113 471639 181191 268574 879509 328257 929795 698773 243692 661441 958590
12 7 827764792
8677 611513 410496 93540 146899 572028 119261
384419 85966 998174 778834 278282 401897 135285
191618 727515 599389 275731 715506 296932 60658
595016 625189 990453 810141 868882 168246 768731
267665 309365 49876 276342 920878 460373 369882
584129 548753 489143 968548 151072 3669 263734
429354 405566 399020 620973 649434 514761 413056
364940 811693 473714 476308 953234 980520 286449
338468 148766 55181 606133 458131 621409 882475
895362 81782 768709 479491 146888 774205 964392
297960 777874 228126 727314 699793 143498 864639
349227 658259 277696 714167 986304 267762 706828
20 3 767993277
794359 913401 564810
916845 887884 186220
799320 783246 784354
84382 779090 931242
858587 743482 229202
152813 487960 472869
368958 631459 337508
718185 806070 131556
948705 792375 915671
655533 248266 680305
165162 558977 593706
729973 475822 481591
916193 791495 781189
700547 875877 560279
148142 250816 820113
377344 403629 308074
850213 772588 455885
704074 7125 261955
351982 472182 570682
267653 127715 335300
12 19 49894277
58017 539203 370100 55960 455396 161595 353502 672295 553824 430133 820437 804640 250247 714134 724622 74673 564347 13562 46910
784773 20687 825217 136756 492870 912252 920761 136937 247552 385072 946167 141830 959442 1722 28283 531754 457118 706230 885256
645766 260055 315390 466203 581047 81989 180337 305669 673014 261037 835583 719924 562162 856271 61493 215270 865493 973745 652384
518782 221298 37456 981302 879480 513250 983024 424115 45005 956495 130346 446613 602261 906753 278355 584816 487800 360344 281506
309822 549710 58895 145405 785986 621057 518028 847480 836328 899873 821225 488712 935008 42523 42520 916310 438356 72123 415686
862471 117128 372181 992817 563741 490794 899570 842097 75611 903723 718793 357117 729897 784856 416012 391654 570842 553421 909683
418322 389749 325908 239548 394813 260916 798423 953686 693578 236779 25809 109265 99251 659289 997798 608420 223030 488593 24343
581479 80556 444418 816625 437673 174315 601481 370037 565969 172323 923458 992004 106998 829560 834265 346546 740725 611533 661321
210763 305112 898101 236572 930729 513704 895861 444879 122124 635244 933472 662819 733075 530380 107237 66052 968053 281552 667533
854442 363874 356209 294253 872230 979559 123813 706495 326105 380890 318029 503778 591654 139493 401879 344578 70222 431935 240440
31453 70412 392036 964926 733231 641463 495306 840469 707516 979712 638373 891401 350506 518599 763962 644759 390830 743521 284924
613677 585978 665815 931706 89757 257469 587551 7988 118399 174125 439924 875191 205579 510336 267227 170505 759919 425043 182163
9 20 101678226
755114 540312 28734 273713 304275 673493 664543 47796 474770 278221 633775 140585 726279 723532 914406 313831 731520 32805 487956 687796
907997 693535 714484 691576 380392 474404 116619 78908 74792 765530 273487 346258 305843 302221 619972 610118 492067 800867 174266 966837
595440 808041 623774 838072 47925 538180 151903 295798 87337 156211 983594 995334 366099 698079 203263 262843 172483 319882 341751 763627
601765 615239 626238 907608 433812 246210 517726 925879 563429 691992 409068 675222 16386 32842 513294 64311 87374 665197 876461 174712
337760 376408 686398 703859 74487 889661 966703 763322 725896 824806 43301 327661 440045 669539 235269 873858 432101 269347 316089 511883
961339 241510 187105 494077 274352 700399 74741 361727 881948 951202 536439 219708 327610 739189 439920 918449 628851 922975 198123 354747
747781 241425 682408 704179 427316 434029 94389 375770 703376 410478 887653 181067 168340 591110 675145 442693 807861 266238 320772 689809
217440 373563 425869 61403 112752 865789 979852 741603 305116 177976 612702 52898 935753 811462 757077 363069 245491 851466 255191 465219
778296 659196 162639 946637 250306 354136 905682 58167 620374 226454 264328 837814 600017 690198 899217 229121 72339 395422 487077 377456
19 20 284946706
509151 911242 703783 388572 673085 71601 643764 654657 849897 302960 817296 312886 69619 171432 218568 644138 308158 445022 908467 662324
561391 115017 77894 306865 703708 473316 793942 597516 563066 893721 544222 72217 321315 248005 977141 510753 835958 137257 165410 685856
956570 499058 998742 26189 186842 733663 186679 495000 695037 611498 157324 772781 726515 235218 79646 946576 224886 873588 544092 787952
283661 88315 860169 121329 852672 353663 632082 688631 490920 313844 890839 447490 812902 405933 473679 516096 139596 176711 11096 834634
788209 684772 607415 514725 436343 203413 977653 661229 77001 521745 449182 877014 610060 825703 998343 462733 179366 630425 151364 670287
944269 42203 117777 273523 448136 107809 789619 104085 800872 317067 938719 589081 1840 62486 620158 954535 265899 597811 615764 859252
119557 64946 736266 729617 890650 734610 708702 586368 881387 376418 256655 342009 418621 890785 615532 383110 514946 921504 487195 315818
754923 942266 904899 273115 4752 41410 227650 787003 639221 843415 646255 758778 424713 382521 4748 315363 633483 713450 901732 514871
89869 674739 856880 24842 81876 988764 924304 596822 426620 927851 428992 697896 870117 850244 971011 391221 891654 715014 178224 530875
558429 340831 806006 499494 239705 327106 331210 873188 556908 749294 904411 646777 424033 277643 187972 505910 782760 628628 619084 209380
556480 48077 423628 426597 898321 394640 817819 306327 109654 512395 837202 184435 853227 159560 683929 92932 486666 15139 482472 43575
764433 386884 206704 704819 180879 911028 210729 963639 539657 346165 689372 96137 910594 113000 522734 808915 23992 856905 115242 133646
885653 468797 834433 738880 628357 518363 348164 631376 49854 346988 674951 814288 733872 398007 519107 431104 309036 246188 394743 848693
108705 84115 461182 19300 713468 983916 344567 737460 357174 976162 387459 242827 444959 221892 498059 589668 740255 846223 737396 306462
193211 412347 120750 443436 326707 156209 874540 635743 918749 785635 788 27454 386103 461970 563106 99571 962238 907674 353383 319412
883836 740842 78591 845147 479087 576650 951167 219342 939225 688564 42156 132437 617263 162906 92225 943970 835467 483117 96065 270568
268752 96853 814375 171207 75175 377481 270778 37414 801507 140514 873178 685343 397708 951770 46842 876795 528420 998010 612490 983998
202926 654646 116435 820189 333905 725012 764160 169372 208129 376577 956293 993233 473431 770668 164441 64958 148149 951571 102372 466009
92085 491903 151352 489794 443673 714547 366589 488445 712557 979079 472443 915483 150078 105230 252024 483983 830242 532536 169707 554723
15 1 429547956
898897
896668
228750
963855
561170
180321
582580
27179
788759
74483
694883
794905
518156
925782
677846
14 20 745173278
995397 70174 323356 616979 838551 807339 963574 371087 977046 518297 796553 619399 66254 695450 516067 811356 175658 593589 991678 758238
137120 296789 832721 348356 91694 867229 274138 285892 906534 428830 459170 418283 15356 298878 35263 853907 106217 998837 741347 599616
517134 537900 219015 99741 233351 251434 427449 409009 361376 419127 683599 14848 232268 32672 363204 840314 899901 637343 126207 322787
582525 585377 741071 597881 400608 292686 968141 506825 291523 709488 622793 325009 247388 358160 941102 997091 609595 368552 922452 487323
304031 606051 502171 52652 638723 381728 892966 54976 535423 19173 377764 117948 120903 635187 715829 521511 927873 200322 544688 735748
909810 167482 577109 673551 525642 518212 670642 651589 403116 593095 655264 223499 715498 157436 276151 870574 539164 169118 925550 74587
704643 819666 708887 825546 971205 941068 863409 899078 141391 408098 151178 51201 91932 728288 724752 617574 762852 911747 785516 165968
21194 440780 905819 253044 114568 181971 123618 170084 867441 565521 761023 572084 901539 469910 397631 872745 410979 261040 288175 552370
185490 955706 119923 277422 683994 361028 411349 446846 272775 196865 129166 810321 153997 551337 63365 784918 249660 703336 955002 117101
268857 716026 689186 686748 185936 603169 559493 113267 380561 364021 665637 566052 319727 785561 843474 520073 662941 771175 483271 935716
968040 128789 262389 638390 680126 842106 423308 929787 545442 378310 46888 814299 610688 252426 501048 312977 855595 576893 426244 236157
457266 608234 318561 293345 910147 678387 813418 573088 449563 296689 25156 417603 941830 287545 572345 138309 129651 995653 68096 675094
890316 631336 5745 17356 400115 23145 330333 772062 116391 272930 8219 573657 881164 843132 867003 307663 521520 196773 880751 971083
9815 905907 905038 951645 193452 993736 89954 839455 989389 674402 30901 396057 822091 36647 929766 222206 59792 776451 994268 176183
2 1 993266193
446897
361972
9 1 465399844
846321
635311
370927
856136
57570
792318
807782
767374
786054
9 11 883291795
88491 637731 204205 426934 674378 133971 649140 250523 910422 159760 943058
476156 678600 725603 439405 556925 375151 193966 956769 221473 345629 844049
593961 403200 636367 918095 170574 938773 332184 293756 230568 937027 931488
951125 363961 122218 85096 529453 889093 511871 689213 348504 504379 884166
74107 943784 957443 965611 137750 914212 187084 999732 274613 297397 919284
427332 215493 606210 366105 547677 899967 113026 1056 347807 64151 881369
986377 665600 410822 391823 177471 616387 740327 681850 500553 330786 141986
457996 296397 796089 888561 999833 795821 163174 297231 715105 106859 512724
837667 989316 576753 737634 102342 577809 601793 682846 459178 588171 348446
AC output:
Code: Select all
Case #1: 12 4157124
Case #2: 20 9682467
Case #3: 272 136301718
Case #4: 255 128110171
Case #5: 16 7336125
Case #6: 196 98672863
Case #7: 280 147075345
Case #8: 228 120737641
Case #9: 152 74091460
Case #10: 42 22451614
Case #11: 90 44888605
Case #12: 28 16080980
Case #13: 38 19846186
Case #14: 121 62912361
Case #15: 16 7882873
Case #16: 128 65251981
Case #17: 25 10600932
Case #18: 96 39253557
Case #19: 110 61934220
Case #20: 55 30634648
Case #21: 56 26103700
Case #22: 10 1736054
Case #23: 14 7830621
Case #24: 14 6485897
Case #25: 95 50708900
Case #26: 76 33295321
Case #27: 38 19892070
Case #28: 7 4222201
Case #29: 78 37798302
Case #30: 35 17894579
Case #31: 42 19495186
Case #32: 85 37225897
Case #33: 108 54169160
Case #34: 117 57082525
Case #35: 126 64003043
Case #36: 54 29633762
Case #37: 60 28488993
Case #38: 114 58243475
Case #39: 99 49726311
Case #40: 180 98033309
Case #41: 84 41082568
Case #42: 60 33720940
Case #43: 100 48943890
Case #44: 180 88279240
Case #45: 380 191372907
Case #46: 15 8814234
Case #47: 280 141413002
Case #48: 2 808869
Case #49: 9 5919793
Case #50: 99 52474348
Check input and AC output for thousands of problems on
uDebug !
brett1479
New poster
Posts: 4 Joined: Tue Nov 12, 2013 4:57 pm
Post
by brett1479 Fri Jan 17, 2014 9:48 am
I used O(n^3).
anando_du
New poster
Posts: 10 Joined: Sun Mar 01, 2015 3:11 pm
Post
by anando_du Sun Mar 01, 2015 3:17 pm
i used O(n^4) got ac . U must prune the search space . nothing else .
Epillion
New poster
Posts: 2 Joined: Thu Oct 08, 2015 11:20 pm
Post
by Epillion Thu Oct 08, 2015 11:28 pm
brianfry713 wrote: Input:
Code: Select all
50
7 10 4361099
372635 403776 757342 613647 255624 827769 988581 15911 261777 184255
78024 387910 348870 200215 585883 814196 380850 444434 610663 873209
210084 734511 355740 416582 27004 585921 880676 188471 270919 377865
549570 643554 781641 823264 257201 553617 167385 762134 85880 945514
946389 680257 333425 811611 396824 919308 625808 777674 363742 236471
167236 90178 487334 522976 506760 514339 108897 387437 219162 379816
765302 285084 23371 63296 624700 796924 133265 792085 559059 219146
20 1 158899402
587376
833412
296227
506684
459220
73901
386778
212043
241137
476956
699377
280466
983717
730068
389363
371154
465582
285532
652808
750666
16 17 283375365
622179 365722 683803 697590 101220 421403 719391 623 525131 69155 813202 548168 528375 403455 934946 256770 160945
411903 472499 441411 911972 718920 347126 799478 184502 632658 968638 935169 974265 201095 826887 112797 83169 510691
810387 184389 448446 46130 701364 973577 115285 514566 521745 160012 918021 456692 933134 595318 384947 405634 36729
813271 124554 383856 612749 309056 532866 581387 760577 23484 298834 587465 136281 382003 98156 463020 82744 62954
25503 784108 36531 140788 815026 558277 817153 249400 531321 750287 844718 432620 155921 881448 245891 796827 781656
374992 622236 314522 956379 382813 854358 771566 486630 990639 153569 101138 970012 236314 164092 995515 536774 200624
652655 351801 275253 469808 601201 322926 736448 445919 755546 408721 843719 517789 205549 625375 892781 827785 456250
849160 726950 310608 620726 213581 817600 290648 314719 787612 43314 478812 299479 580088 195788 952134 448241 471041
938295 49442 793967 674743 11714 65865 83464 855433 583654 289013 997161 476435 633150 453411 841947 360101 280371
979026 90034 97971 269674 404753 401935 829340 399917 701414 409428 595705 653549 374022 583098 108196 423464 377065
782939 951530 442930 866403 323316 542936 671769 320477 19371 821271 290240 861319 697724 570611 840345 787758 184935
626371 708864 586870 455711 108781 804637 381491 704487 974538 271865 803937 82734 695330 181003 865673 163212 140285
248428 486528 683222 920197 323357 218945 257821 613597 80264 955545 700561 436961 259656 401848 579684 968520 505070
551747 593653 309707 449591 814492 284245 721456 618430 366979 933138 315785 749004 96351 456070 997433 99231 655644
433982 422589 874590 691803 552538 471206 163701 769451 424520 939709 171299 4204 424581 192722 72304 18234 502429
521895 349079 303027 243351 967509 186358 692842 283294 935363 789193 255716 932796 404776 427713 366778 827365 818655
15 17 370289860
254987 182059 714381 194696 869711 234938 619277 62433 307242 153863 81214 829137 502942 384241 588840 470451 570600
281682 270097 22315 587227 42166 955111 992004 469879 838241 335721 288534 929527 748329 94747 184514 930389 325481
895562 800100 560419 514839 378885 384013 185055 460099 729502 687997 360693 318342 674801 931293 116377 944898 469960
219956 987064 425071 728312 973295 779664 580386 778181 225544 328715 872929 410058 775456 198410 821973 91908 275181
336812 470793 659194 38219 930893 905048 726217 807938 739742 401018 255583 856119 862268 725543 592428 365685 666966
320740 338980 446630 417478 117162 672174 746194 506443 598585 38002 221205 420558 129911 12738 273722 117056 188284
311942 564301 93332 554511 372239 833074 955529 627822 205546 817797 353365 797974 183482 20331 635066 38815 983314
52545 672329 171840 315091 695124 770425 869445 916329 707335 515708 445419 497410 632765 633703 325704 197066 727035
880215 569306 76461 352096 713480 282007 686245 66846 596333 386080 603529 747752 424895 586843 316649 613576 758684
148092 308700 45461 17537 225029 269149 533246 670448 282911 166011 820503 608615 879429 547538 5182 965087 140351
873630 678568 422359 559875 261766 535044 945955 865295 799148 887202 968491 115797 500778 727175 263889 809478 288988
281427 550859 74489 331025 737659 357400 497036 558162 482367 376465 622052 487549 341553 762404 361179 536473 701115
921055 798239 752511 383362 663534 551660 270565 148377 667457 771343 391904 931347 580822 680893 729126 131681 755382
60151 869341 629135 73539 943855 111502 966356 565908 115404 824261 328312 476583 360734 545779 913990 158973 298290
813705 338860 849950 84270 487237 517408 371965 879142 965107 469139 76387 210585 117173 348121 270736 502866 977256
8 2 391605111
826983 12629
720515 651245
857293 197098
11979 403072
627441 687305
701363 441146
542517 67665
41768 546106
14 14 892425247
66532 882873 17987 277117 46 366109 64205 502912 859717 924832 465985 464828 268168 478615
701695 919413 852260 898794 447744 255333 42587 135049 473048 85 193918 540713 41853 740025
642139 971938 681625 708671 854811 699613 502141 371209 582074 82698 390473 958143 523883 856459
422972 792051 851426 641019 227816 703686 539813 675560 475371 98752 326962 948419 98837 520880
5485 657042 777257 647624 628981 458883 872647 144 674848 891140 371354 256922 973839 278179
215065 497722 134638 154389 806125 502416 311761 33941 206103 851574 225853 681474 466679 552815
629894 565516 590048 151731 222559 883657 799355 367892 342540 672002 368036 533740 79495 739390
790662 53334 533922 522080 67408 184912 192821 873533 687329 504582 423826 893432 872509 649679
574906 855540 718847 721152 937408 825247 872883 676319 708904 188590 44211 567797 376945 412248
101537 456440 667990 408552 509774 201912 446984 577182 386825 156157 967067 74154 177092 390893
483938 565953 556924 575196 421493 275771 296349 875253 101018 685584 551573 326275 390527 595784
894072 767472 524384 511961 223912 192375 436865 250038 394287 400201 343572 297464 556359 826991
887970 249803 217884 371908 815756 291160 947105 753601 566932 759806 628854 184302 961742 696779
510577 352269 292564 921001 636093 816948 949315 376357 525675 902532 142747 436315 302734 486319
20 14 188829662
621750 625248 563898 510010 957356 855059 457115 227309 421991 733273 856163 122645 695016 552943
633223 563637 361859 70576 199731 695159 536243 92440 220835 438776 235188 657150 741510 237859
907281 116955 67522 45383 742203 631420 555394 215911 486479 528861 443220 908470 262135 299383
547468 473503 368678 180691 553492 246889 767619 269575 942049 820215 362016 679236 258991 597204
336386 501 835063 243667 633808 902585 805403 892363 534006 360797 108274 536837 406010 551494
445308 184497 367229 992776 658000 252260 689819 727845 499149 973790 997420 957550 794005 359436
636786 569348 472992 973172 569849 308056 733192 720009 726993 54947 612372 777351 415744 720646
314189 338106 272140 275849 522604 639370 268625 696956 891630 474796 424801 907131 964938 422222
864682 275296 298010 501468 844644 771003 990993 930846 595411 240537 650855 322404 295484 779580
616108 227580 500226 930297 82038 288719 206146 604642 444441 991123 301599 852423 982271 242752
759554 947209 181326 140588 222505 479337 158409 583502 766692 149402 514348 878455 906291 165203
717211 718127 461135 333319 462059 961362 263616 544097 766433 469762 665092 210874 460885 966691
63297 443156 725795 339203 906718 907122 479792 129223 902811 638201 712725 669503 303955 743425
547958 210246 424981 781521 444725 886116 114841 423136 847478 378457 967233 613911 848220 632325
341137 825457 115368 920786 268614 357516 259990 175332 264638 739782 820907 167449 894335 49985
353304 198290 793410 417614 924888 734743 199135 885965 620860 313976 309101 984690 692434 792686
114954 57006 941364 456091 882463 573084 376878 667429 930600 636868 359113 195238 893002 180021
362687 303689 746358 232343 501979 56120 649957 943219 790864 849093 829184 411724 163069 654637
396414 855503 447323 27720 428861 388687 483812 311325 478124 377042 495106 408724 530262 854220
603963 939616 550593 483002 243305 296951 715346 261636 353071 365303 204855 143935 214396 550391
12 19 735721380
984778 265673 685055 12498 694535 590095 12662 522212 68219 389704 17318 476943 436318 387890 597258 375934 938483 80261 135591
751786 311959 397227 104858 193614 118434 765145 924363 185177 353509 818181 906557 338287 83854 591613 867137 294741 181708 879800
816953 766279 785856 350624 243222 738527 738514 840481 630813 676998 437094 766405 945136 265405 163632 49994 459019 798419 331492
383382 499948 201353 717915 922858 539640 801770 514471 923129 96511 212531 319281 429817 495162 621490 780441 738384 360017 518955
95217 990830 712305 48663 757235 657442 314068 437220 223788 773088 751991 71632 672822 251939 272985 390738 174797 328977 708860
205620 252107 321723 934503 87740 751540 429665 709230 531981 684402 69247 567289 779619 576430 795946 828283 333665 969740 658703
287237 709881 948143 39228 781513 620966 807520 570851 528056 982317 416180 236916 704290 184639 558639 638793 272380 826532 584811
981610 358513 269213 567210 442154 565184 143640 754453 909819 993657 240545 568523 280895 950426 33018 836475 248292 653984 643995
335495 698392 142665 751675 451660 846955 936315 526652 2100 208695 353184 586911 706657 228049 372476 273867 670204 937661 933859
941009 363832 927517 181554 932355 724764 648333 965374 561239 896625 135710 721587 232120 350455 380604 500147 802115 743911 436462
328767 746011 161509 681951 849275 384519 910001 738103 174738 96557 675764 108598 553918 555949 552467 735472 488304 277231 900157
970030 838470 796782 622093 76409 545254 972548 457013 561754 774663 200924 514568 619783 463288 676078 301734 828915 576949 728087
19 8 432340996
759135 376637 894914 315084 929104 146739 319740 206335
46896 806123 561158 360031 944568 637567 905285 917116
610933 983391 208131 328209 497960 344266 307849 690390
646001 136764 267339 890440 220135 535378 231437 495622
912016 126351 327058 841120 789442 646798 563808 836339
969273 124966 196370 913841 278885 618007 347309 406170
601399 555441 734380 99359 899707 558581 306101 62060
211698 573440 468853 431833 625170 700290 443807 537186
342993 770865 894659 132436 417663 458467 968775 903289
99785 681497 817130 378670 299504 164440 784841 417255
236233 35573 32966 652292 594154 339067 714353 805852
428859 183206 754037 54030 399848 197844 591216 259193
968709 485875 391629 902725 460694 876756 806014 560479
74605 139496 455502 374110 303936 240343 791365 56521
792268 340684 708814 386422 679751 939519 192275 108611
122725 462664 162641 38925 660509 270209 298118 629218
272437 206100 531943 733131 82856 854309 809963 673814
993806 265465 47924 814094 22160 355641 386968 814428
696325 95782 200850 892429 35301 909477 1040 674378
3 14 521713302
549003 950242 527773 178221 739031 733873 226517 472163 333082 80826 798478 6896 590984 580295
571172 921431 602455 926813 308399 416883 139491 404181 134085 548272 955834 559915 65664 146564
448409 745697 859867 997412 212291 387640 175633 951323 121514 918502 939838 970948 515681 738316
5 18 847318610
549016 544448 437418 992181 369199 854301 131672 773380 504738 196296 245566 581005 261960 392130 29414 7657 768349 26826
219949 672342 718812 687624 310208 637314 627462 281156 669347 882130 259000 292365 717093 808016 836813 154511 800197 206013
525164 448222 495745 546254 644518 257664 127260 422831 166146 156674 430488 934496 699853 166789 606838 418665 370765 917046
572331 998227 714554 241679 396709 973554 50396 630154 297922 887209 784665 614471 609574 826181 62693 621672 888788 223564
879336 16048 646395 45482 689074 593235 496330 388927 276377 619520 323944 647142 52918 896276 161722 767472 654307 558431
7 4 41188584
555300 108264 489603 169772
717839 832137 748817 855863
720925 488733 251551 253325
651480 813385 942399 244716
309716 331327 521093 929236
655271 684587 982155 67899
846309 265979 722206 921093
19 2 402626031
78658 51526
631986 248430
285717 464123
513600 141580
701400 2333
393131 954725
653814 722868
897125 898530
32584 744804
935975 478173
916427 620562
976680 500679
983224 242659
222885 904317
766017 682499
530348 361028
734025 162334
609458 536094
142810 123058
15 11 65641744
587157 798936 295558 826377 212413 710440 858962 473569 646415 853487 389996
783329 346519 890675 282905 589178 629913 703574 871548 312412 233922 232576
562789 912609 358386 98883 571771 997797 292909 415981 639541 396418 731269
451451 222795 460034 161891 598109 933603 324658 451596 839952 624339 798115
730627 907245 903646 876892 610819 291546 705656 361094 40474 268445 790055
915212 883680 361826 429361 176589 294159 68902 573007 541781 520353 312155
1815 198596 910264 451771 523254 878213 291723 147594 192680 538702 54839
96326 415595 665658 904224 121251 543104 944698 906049 333159 376263 789729
694985 805624 966319 989145 390879 55678 530926 427584 884185 49093 626181
794450 500864 149435 672663 308939 297029 381695 847642 351868 478022 779589
533879 898598 900840 593335 359649 806889 926495 735912 596619 621480 541536
79290 126977 448767 651320 174255 876352 51858 223349 502533 846308 240565
651968 35323 549505 465350 417018 913499 333570 411392 693088 867449 309991
110280 460785 185992 917170 903632 921904 30141 525112 979792 625783 168442
428560 793455 342697 821264 845313 82398 323797 207973 839316 492117 759648
2 8 52693019
818672 291038 104411 511760 674839 930754 138392 651976
116746 55562 555608 555002 602055 597073 534795 744190
16 8 468053998
624564 300971 899311 706963 624768 623637 546279 633237
383285 451452 590705 76304 270124 398095 697068 298236
72934 627822 436628 724911 260921 8543 280519 815923
126950 877592 867070 387493 159459 346777 441491 784024
647748 857154 7339 788868 480791 69970 422106 380429
37774 529163 456733 824250 927258 153801 122486 192
297976 75466 725103 558897 600361 521975 891172 727312
915919 758243 114805 591731 105020 72648 892107 269121
929802 899446 57989 410594 485768 996447 791023 523542
525610 764108 347792 452868 434262 986630 453061 732238
62096 694516 807487 662458 732843 215011 906122 648763
973254 537279 240494 594627 609927 132601 863748 539729
548399 438089 466675 34167 434537 774050 557709 960147
54511 421853 929368 488773 408483 382429 737363 470579
593297 544850 649389 326141 759861 71863 491256 249468
609142 248102 844095 219069 897055 224195 275151 961806
5 19 10995971
96821 548581 70034 573321 603092 8239 502689 91865 416722 401470 829228 403653 994767 890430 569395 837260 166643 641258 844868
416111 250401 92970 776558 985822 506377 753 777325 468183 663038 35504 980508 276211 100437 566894 849532 703529 575133 868573
311746 508207 270043 140974 911861 781163 547756 481256 134775 714399 122514 979644 646863 889267 588966 939773 875090 611696 940527
168767 79879 119917 720623 576740 396128 821060 143634 762013 524589 235120 630586 836335 259679 900630 493661 171540 681793 41417
169148 816568 272169 808015 312564 435384 697282 901531 375157 88724 513227 832036 257492 109458 951953 978115 686198 348082 799176
6 16 537840117
97657 740681 676453 357336 157663 686466 45229 839456 244236 214377 172377 516405 22392 484941 468141 236027
902824 843298 324751 932403 191687 582243 41862 143640 76711 244412 491722 392239 106949 118169 232356 204606
375203 425161 78295 532866 111628 123524 888675 355864 854253 61052 388621 392998 62345 373114 629025 481522
732764 953776 413925 924451 52372 972139 68092 645435 216552 76166 37674 323501 194336 270030 44460 85891
211544 639107 618757 323172 762631 23784 195388 133236 601188 100361 526234 663534 473475 155259 661408 206239
625388 75333 130691 194112 563825 715135 839547 780377 791301 877221 620230 501989 663603 181042 587880 875147
10 11 765198318
99132 746774 910059 748721 347963 10420 274955 527849 483895 946567 189257
206487 571955 780942 853530 766067 344767 568665 605614 641496 359966 999187
778079 378308 662790 959121 966188 537938 295623 205530 252609 911107 952305
162669 659828 816620 689441 934784 860821 689689 397703 566430 896176 969658
347372 266058 252077 208492 834723 374043 366340 711041 889582 660771 89349
552372 136245 571890 606662 431868 777420 375624 342975 246077 54645 519156
579049 744086 970292 439870 950127 367995 6300 846303 854005 870025 628713
106082 594869 463436 996477 961209 174478 886059 621981 780179 954783 758226
352069 77798 706446 645842 453422 565773 891919 508067 84929 470969 768505
55221 910839 718633 423216 433492 81288 277221 303517 710002 899655 898386
11 5 652375947
864268 298543 514280 160800 769679
788858 512869 847477 495304 158711
817251 61078 566983 841670 662359
37952 610175 717581 465143 845160
657149 898635 442801 934371 718504
669155 350378 616890 358945 762863
509190 739566 577758 23470 900366
347437 812329 413235 711266 307633
88299 528517 885063 655282 370187
547423 209586 496715 781356 191081
858227 438505 606069 301028 889228
14 4 57239605
457816 329129 518822 967006
585047 96580 506828 485413
960370 319157 415000 671636
143143 19651 200154 544558
674933 86693 91981 400871
583408 389689 591953 441636
828195 198022 742664 233775
38947 229200 989734 496763
74681 508556 980121 659728
121489 486950 661493 81859
806107 592845 753495 465602
612497 470001 10161 287430
556695 618494 688302 656455
8184 796607 614443 352731
10 1 48586504
33576
102660
92593
46692
693693
117501
26813
353421
238990
30115
7 2 739836222
124111 107049
818177 736608
577050 828338
540391 650097
446833 745045
822905 455017
541652 437348
1 14 740310808
426958 602561 413468 519551 649253 107161 637053 192419 976934 392395 222534 24552 745949 575109
5 19 907393287
885272 946400 221625 942015 112850 184810 687060 935755 639827 745064 373103 480279 797697 200264 907238 400259 130084 426789 565864
753598 580194 274635 730532 488942 13522 755085 234891 588631 420101 604241 981918 821725 66993 719896 763741 179843 904706 450801
115598 60886 195866 5054 541165 509915 721670 448403 426526 851754 391545 508743 605352 488091 783378 852237 493385 313252 123674
244628 901884 543775 365221 400154 365500 432215 636402 645593 612058 541109 96395 244009 118347 808613 765415 659512 834880 487085
624268 261407 338839 532165 286502 944192 536608 586232 796429 546346 899485 920103 790974 801369 980230 156196 717875 345730 588411
19 5 34716820
411739 604071 477182 530086 929036
242597 705950 280268 729682 846570
58027 584874 378735 344529 45418
431696 930762 841847 978042 830247
278302 285368 147968 774884 957916
865843 636966 62679 736473 628290
779501 148212 748713 256683 678298
194101 15633 384249 474370 745315
230819 532397 846541 125907 393279
891959 73955 840393 250158 568349
186992 44812 853717 334960 819696
327986 717155 456663 390665 969981
601305 686518 118193 350019 943202
312844 60472 958835 697093 51194
220502 444264 99944 583396 86523
493223 475355 160478 333616 725514
728827 36960 770326 98897 888272
590023 426883 121779 46686 817548
91760 647991 504067 209954 514362
2 19 230091186
438808 736243 658733 175662 696859 758677 759058 783383 768252 234414 460213 618220 476280 189041 655180 246606 804290 543452 352981
231173 665232 916019 565073 756992 80363 585492 483298 111077 549113 522448 202264 504273 258691 860998 679936 471903 136027 955346
7 1 402706112
715499
522500
182392
420892
694033
945351
741534
6 13 560489059
419069 730704 54133 176062 811067 155977 175712 922144 221443 698161 640761 725716 473204
18111 922004 461459 154138 393703 716745 574770 99815 948597 97271 282208 885841 307656
743911 143728 545141 42243 632787 964211 772947 203272 656625 100366 359250 348689 538863
580693 46850 179624 822761 36407 714087 261118 497866 384577 654821 730964 959348 270988
195913 572971 553196 598106 880627 813459 741834 425768 855703 374622 906331 145002 94246
79308 761721 453496 427998 300584 550541 991200 996560 889655 27607 710647 150773 41826
5 7 424289141
54572 592934 1407 627543 662483 599513 24522
475942 857700 450291 847997 232322 872974 509352
842920 952283 271073 296417 380281 571657 363310
371481 568217 252965 915441 795216 920090 473619
890440 242036 279113 461365 351323 280520 605260
7 6 402629782
489748 254085 596426 337746 2759 469400
847098 845680 938035 634523 142097 318316
206180 21759 206150 290749 791077 637943
602317 711167 627914 9109 469556 907027
470474 820879 187547 592087 834685 583932
738222 324433 354370 334648 178531 357129
320400 541981 202809 258436 176504 861258
5 17 108883017
815606 706137 674095 453549 308454 385262 81463 317564 854818 504842 304390 675697 208741 896477 26734 792674 634699
867520 147044 485699 46051 20525 806100 104385 223335 580888 280889 84593 190344 179926 967611 5951 886063 158058
975852 710870 59673 573668 28434 430843 78510 332824 622893 287252 745654 649627 596278 896705 517147 259674 382405
79551 280199 704857 183936 503534 285745 464825 588128 992441 161103 72091 998392 563519 230150 974245 274389 806175
64265 819175 237018 142775 668351 859911 430027 414005 25891 26305 827063 59390 802331 209468 138941 82531 430677
18 6 274232774
304055 690545 225215 981510 278989 223608
545029 25491 714205 335770 831666 778470
154945 68684 437597 339649 444948 867625
753654 987191 410282 97069 46581 212614
822889 185523 811497 253566 24752 397562
486340 845159 604460 711556 826670 883449
451516 888051 908940 682073 740174 740606
976895 411471 325642 414492 751120 286942
798469 21127 274133 725104 118196 320715
454070 941086 22590 265567 711004 47342
663129 197345 892502 267589 425253 235524
667390 393121 639927 576330 75194 896453
316936 52089 307925 158931 982933 59045
445873 297755 596524 720007 22859 714721
557074 476929 172159 579664 742496 883163
627006 921977 596860 35860 705919 538465
787736 373309 931586 944016 949640 6780
840469 266576 575221 148394 941859 74507
13 14 57372261
320316 107740 395121 551389 181166 388402 239900 760830 130898 123064 904188 52875 236276 456401
758794 774742 244137 132104 222680 704505 81744 745813 544975 864672 837386 209721 806532 911893
449865 710617 284155 770182 334709 195628 837923 515875 584030 77824 276705 231280 717240 697245
800508 953516 153646 559302 244610 914136 207758 467291 618641 805854 213104 679968 186879 50490
889690 993411 478736 339555 220380 762891 626089 555089 474872 464013 70964 575254 541837 864021
806535 259077 561266 123395 728945 714913 682697 973556 145401 406808 957199 764042 212662 170303
444011 399541 737145 850053 909304 215881 189608 129684 495125 332050 684773 486349 796063 272089
61603 854252 136110 384490 629681 213729 507885 358626 444994 706935 848534 590395 113743 805733
870789 842757 492388 314800 242299 745886 681205 667955 961767 387166 313992 456892 719216 515117
943241 515279 787207 521197 885883 439669 422039 515564 169750 446277 390542 614744 153212 239077
205139 783307 561162 75929 626064 569903 907081 384715 315789 588287 52671 277556 975453 883015
250801 211021 398132 710394 726300 701691 747943 128535 657713 169983 644099 827463 616260 550993
442208 285824 790070 163699 69131 867585 755980 211547 437488 663062 596263 269629 767701 165286
18 7 348048300
830690 470527 962785 541085 713179 664477 805380
841714 322190 975363 2165 149653 107975 553158
108213 910151 859581 271913 979282 243518 27893
707182 197358 690955 303445 466987 975008 985083
530524 234514 33384 361215 221393 996169 418652
934572 176998 224032 292638 499188 715748 294803
165194 340075 364314 273407 250227 223895 545320
745861 467413 573214 453043 664771 780521 756488
648110 755530 257923 694986 506396 291307 56201
727790 803829 991205 178714 980827 215238 471353
996368 447338 282508 161562 787413 646822 951321
37640 387069 496642 783502 370834 586208 236545
551957 883081 509386 200067 638611 767309 895054
661360 574969 467607 905502 895150 458813 84216
392329 190403 71921 388697 637741 354430 66611
425154 517604 17933 979147 421026 30927 762649
791860 133487 515546 860170 16568 541284 60237
655180 824946 471643 832892 399915 455603 738394
6 9 611338961
203746 621171 927236 592444 775264 798018 175407 716770 315622
709692 695917 253000 256971 458566 561213 390458 490465 421383
407027 31749 997972 578559 856695 469616 411451 772962 441571
666197 584379 872339 521511 788126 493510 448747 896922 785126
246765 588681 501896 78740 298374 197814 331740 555345 172732
892953 945804 663197 830688 869183 211299 828661 447742 584346
10 6 979357308
256200 41742 458040 644891 79605 762518
138401 528353 659440 923527 291470 248122
941775 886562 62848 139589 734655 134545
312322 143960 596701 491871 974649 465884
703170 319662 913626 803869 134291 289171
677530 906843 847265 135570 551734 926871
898089 206487 971576 73881 646366 779398
322003 588141 665961 901203 727731 400616
35749 556405 544576 632450 48276 35577
98335 267799 355239 528313 71668 5882
6 19 666912725
664750 401120 464459 107973 299209 670946 79549 373091 833664 858948 211446 421806 41261 112650 149537 441877 148399 222294 502805
780849 270570 54735 395536 538369 409974 923850 126389 415857 257687 875587 844934 438789 276708 309394 546763 92269 496692 142664
981712 330357 517964 193159 752163 559225 822161 418052 517454 970560 640346 536612 267761 427268 591347 663298 481990 517673 103500
608379 449882 361187 319 294817 799976 793379 604211 346739 885648 617255 5756 383713 463964 523720 576872 732479 82946 399033
666883 600400 885945 823581 653364 670058 250850 244711 849708 732840 762385 953208 857571 728619 830747 857890 23436 630724 651269
143999 493815 53270 761255 499571 953335 741571 539644 46559 474051 622590 961944 140934 739342 847889 964516 909059 517947 731718
11 9 470464557
432507 837216 322129 161127 667964 696372 700915 815040 863993
844915 825207 433615 122522 841131 386950 864093 380775 433509
338144 519717 395453 995431 259059 243342 476299 168118 277642
208017 838241 161650 672575 787100 515218 511056 948227 699534
207428 649143 514574 587774 10410 339782 21389 132932 180913
408340 513377 78040 841849 851522 597757 237303 363305 373168
996997 839604 541287 790991 47621 895880 468993 236548 682980
984212 263956 147560 200098 471385 313055 714673 575511 839817
570807 596900 972749 268072 5240 486126 346112 363442 854000
943869 117097 733657 317037 630446 573261 374676 421438 137234
786908 406783 373782 986241 390995 637739 133801 107446 625476
9 20 905200986
803025 909278 314239 292126 693702 835832 778252 39814 199274 148605 500035 832723 882262 333424 463169 971876 224453 400959 109110 527713
807743 999245 513954 715090 636984 164107 822536 778812 127315 161007 496151 446692 586637 810390 738818 280339 162574 517071 836505 878200
182028 852892 710923 64290 186317 690445 552518 927122 607756 661629 454835 931851 177226 968790 646942 330562 132897 985830 109374 776565
663190 121877 223257 249827 448619 962076 46519 611194 995499 883024 489394 177527 735917 716670 758169 438586 407115 310688 882060 531223
488669 336895 463075 665895 822037 626369 996457 471287 612199 622183 247852 791741 744060 471109 557921 192679 949537 604440 320225 945036
487464 809620 638915 739733 42642 397085 694671 966109 224125 576731 497332 229146 429979 960407 411393 252016 586776 924202 723303 715328
62737 971155 507069 806797 958617 64990 515828 908154 669430 836054 369543 673247 162026 8458 929332 204668 921895 624004 170777 146020
200735 184461 891518 147066 144869 819263 399083 731645 743465 638738 446973 806202 609894 470395 129351 84863 535385 161532 509369 721168
513938 878912 394415 675964 887371 840099 396984 809266 464103 84113 471639 181191 268574 879509 328257 929795 698773 243692 661441 958590
12 7 827764792
8677 611513 410496 93540 146899 572028 119261
384419 85966 998174 778834 278282 401897 135285
191618 727515 599389 275731 715506 296932 60658
595016 625189 990453 810141 868882 168246 768731
267665 309365 49876 276342 920878 460373 369882
584129 548753 489143 968548 151072 3669 263734
429354 405566 399020 620973 649434 514761 413056
364940 811693 473714 476308 953234 980520 286449
338468 148766 55181 606133 458131 621409 882475
895362 81782 768709 479491 146888 774205 964392
297960 777874 228126 727314 699793 143498 864639
349227 658259 277696 714167 986304 267762 706828
20 3 767993277
794359 913401 564810
916845 887884 186220
799320 783246 784354
84382 779090 931242
858587 743482 229202
152813 487960 472869
368958 631459 337508
718185 806070 131556
948705 792375 915671
655533 248266 680305
165162 558977 593706
729973 475822 481591
916193 791495 781189
700547 875877 560279
148142 250816 820113
377344 403629 308074
850213 772588 455885
704074 7125 261955
351982 472182 570682
267653 127715 335300
12 19 49894277
58017 539203 370100 55960 455396 161595 353502 672295 553824 430133 820437 804640 250247 714134 724622 74673 564347 13562 46910
784773 20687 825217 136756 492870 912252 920761 136937 247552 385072 946167 141830 959442 1722 28283 531754 457118 706230 885256
645766 260055 315390 466203 581047 81989 180337 305669 673014 261037 835583 719924 562162 856271 61493 215270 865493 973745 652384
518782 221298 37456 981302 879480 513250 983024 424115 45005 956495 130346 446613 602261 906753 278355 584816 487800 360344 281506
309822 549710 58895 145405 785986 621057 518028 847480 836328 899873 821225 488712 935008 42523 42520 916310 438356 72123 415686
862471 117128 372181 992817 563741 490794 899570 842097 75611 903723 718793 357117 729897 784856 416012 391654 570842 553421 909683
418322 389749 325908 239548 394813 260916 798423 953686 693578 236779 25809 109265 99251 659289 997798 608420 223030 488593 24343
581479 80556 444418 816625 437673 174315 601481 370037 565969 172323 923458 992004 106998 829560 834265 346546 740725 611533 661321
210763 305112 898101 236572 930729 513704 895861 444879 122124 635244 933472 662819 733075 530380 107237 66052 968053 281552 667533
854442 363874 356209 294253 872230 979559 123813 706495 326105 380890 318029 503778 591654 139493 401879 344578 70222 431935 240440
31453 70412 392036 964926 733231 641463 495306 840469 707516 979712 638373 891401 350506 518599 763962 644759 390830 743521 284924
613677 585978 665815 931706 89757 257469 587551 7988 118399 174125 439924 875191 205579 510336 267227 170505 759919 425043 182163
9 20 101678226
755114 540312 28734 273713 304275 673493 664543 47796 474770 278221 633775 140585 726279 723532 914406 313831 731520 32805 487956 687796
907997 693535 714484 691576 380392 474404 116619 78908 74792 765530 273487 346258 305843 302221 619972 610118 492067 800867 174266 966837
595440 808041 623774 838072 47925 538180 151903 295798 87337 156211 983594 995334 366099 698079 203263 262843 172483 319882 341751 763627
601765 615239 626238 907608 433812 246210 517726 925879 563429 691992 409068 675222 16386 32842 513294 64311 87374 665197 876461 174712
337760 376408 686398 703859 74487 889661 966703 763322 725896 824806 43301 327661 440045 669539 235269 873858 432101 269347 316089 511883
961339 241510 187105 494077 274352 700399 74741 361727 881948 951202 536439 219708 327610 739189 439920 918449 628851 922975 198123 354747
747781 241425 682408 704179 427316 434029 94389 375770 703376 410478 887653 181067 168340 591110 675145 442693 807861 266238 320772 689809
217440 373563 425869 61403 112752 865789 979852 741603 305116 177976 612702 52898 935753 811462 757077 363069 245491 851466 255191 465219
778296 659196 162639 946637 250306 354136 905682 58167 620374 226454 264328 837814 600017 690198 899217 229121 72339 395422 487077 377456
19 20 284946706
509151 911242 703783 388572 673085 71601 643764 654657 849897 302960 817296 312886 69619 171432 218568 644138 308158 445022 908467 662324
561391 115017 77894 306865 703708 473316 793942 597516 563066 893721 544222 72217 321315 248005 977141 510753 835958 137257 165410 685856
956570 499058 998742 26189 186842 733663 186679 495000 695037 611498 157324 772781 726515 235218 79646 946576 224886 873588 544092 787952
283661 88315 860169 121329 852672 353663 632082 688631 490920 313844 890839 447490 812902 405933 473679 516096 139596 176711 11096 834634
788209 684772 607415 514725 436343 203413 977653 661229 77001 521745 449182 877014 610060 825703 998343 462733 179366 630425 151364 670287
944269 42203 117777 273523 448136 107809 789619 104085 800872 317067 938719 589081 1840 62486 620158 954535 265899 597811 615764 859252
119557 64946 736266 729617 890650 734610 708702 586368 881387 376418 256655 342009 418621 890785 615532 383110 514946 921504 487195 315818
754923 942266 904899 273115 4752 41410 227650 787003 639221 843415 646255 758778 424713 382521 4748 315363 633483 713450 901732 514871
89869 674739 856880 24842 81876 988764 924304 596822 426620 927851 428992 697896 870117 850244 971011 391221 891654 715014 178224 530875
558429 340831 806006 499494 239705 327106 331210 873188 556908 749294 904411 646777 424033 277643 187972 505910 782760 628628 619084 209380
556480 48077 423628 426597 898321 394640 817819 306327 109654 512395 837202 184435 853227 159560 683929 92932 486666 15139 482472 43575
764433 386884 206704 704819 180879 911028 210729 963639 539657 346165 689372 96137 910594 113000 522734 808915 23992 856905 115242 133646
885653 468797 834433 738880 628357 518363 348164 631376 49854 346988 674951 814288 733872 398007 519107 431104 309036 246188 394743 848693
108705 84115 461182 19300 713468 983916 344567 737460 357174 976162 387459 242827 444959 221892 498059 589668 740255 846223 737396 306462
193211 412347 120750 443436 326707 156209 874540 635743 918749 785635 788 27454 386103 461970 563106 99571 962238 907674 353383 319412
883836 740842 78591 845147 479087 576650 951167 219342 939225 688564 42156 132437 617263 162906 92225 943970 835467 483117 96065 270568
268752 96853 814375 171207 75175 377481 270778 37414 801507 140514 873178 685343 397708 951770 46842 876795 528420 998010 612490 983998
202926 654646 116435 820189 333905 725012 764160 169372 208129 376577 956293 993233 473431 770668 164441 64958 148149 951571 102372 466009
92085 491903 151352 489794 443673 714547 366589 488445 712557 979079 472443 915483 150078 105230 252024 483983 830242 532536 169707 554723
15 1 429547956
898897
896668
228750
963855
561170
180321
582580
27179
788759
74483
694883
794905
518156
925782
677846
14 20 745173278
995397 70174 323356 616979 838551 807339 963574 371087 977046 518297 796553 619399 66254 695450 516067 811356 175658 593589 991678 758238
137120 296789 832721 348356 91694 867229 274138 285892 906534 428830 459170 418283 15356 298878 35263 853907 106217 998837 741347 599616
517134 537900 219015 99741 233351 251434 427449 409009 361376 419127 683599 14848 232268 32672 363204 840314 899901 637343 126207 322787
582525 585377 741071 597881 400608 292686 968141 506825 291523 709488 622793 325009 247388 358160 941102 997091 609595 368552 922452 487323
304031 606051 502171 52652 638723 381728 892966 54976 535423 19173 377764 117948 120903 635187 715829 521511 927873 200322 544688 735748
909810 167482 577109 673551 525642 518212 670642 651589 403116 593095 655264 223499 715498 157436 276151 870574 539164 169118 925550 74587
704643 819666 708887 825546 971205 941068 863409 899078 141391 408098 151178 51201 91932 728288 724752 617574 762852 911747 785516 165968
21194 440780 905819 253044 114568 181971 123618 170084 867441 565521 761023 572084 901539 469910 397631 872745 410979 261040 288175 552370
185490 955706 119923 277422 683994 361028 411349 446846 272775 196865 129166 810321 153997 551337 63365 784918 249660 703336 955002 117101
268857 716026 689186 686748 185936 603169 559493 113267 380561 364021 665637 566052 319727 785561 843474 520073 662941 771175 483271 935716
968040 128789 262389 638390 680126 842106 423308 929787 545442 378310 46888 814299 610688 252426 501048 312977 855595 576893 426244 236157
457266 608234 318561 293345 910147 678387 813418 573088 449563 296689 25156 417603 941830 287545 572345 138309 129651 995653 68096 675094
890316 631336 5745 17356 400115 23145 330333 772062 116391 272930 8219 573657 881164 843132 867003 307663 521520 196773 880751 971083
9815 905907 905038 951645 193452 993736 89954 839455 989389 674402 30901 396057 822091 36647 929766 222206 59792 776451 994268 176183
2 1 993266193
446897
361972
9 1 465399844
846321
635311
370927
856136
57570
792318
807782
767374
786054
9 11 883291795
88491 637731 204205 426934 674378 133971 649140 250523 910422 159760 943058
476156 678600 725603 439405 556925 375151 193966 956769 221473 345629 844049
593961 403200 636367 918095 170574 938773 332184 293756 230568 937027 931488
951125 363961 122218 85096 529453 889093 511871 689213 348504 504379 884166
74107 943784 957443 965611 137750 914212 187084 999732 274613 297397 919284
427332 215493 606210 366105 547677 899967 113026 1056 347807 64151 881369
986377 665600 410822 391823 177471 616387 740327 681850 500553 330786 141986
457996 296397 796089 888561 999833 795821 163174 297231 715105 106859 512724
837667 989316 576753 737634 102342 577809 601793 682846 459178 588171 348446
AC output:
Code: Select all
Case #1: 12 4157124
Case #2: 20 9682467
Case #3: 272 136301718
Case #4: 255 128110171
Case #5: 16 7336125
Case #6: 196 98672863
Case #7: 280 147075345
Case #8: 228 120737641
Case #9: 152 74091460
Case #10: 42 22451614
Case #11: 90 44888605
Case #12: 28 16080980
Case #13: 38 19846186
Case #14: 121 62912361
Case #15: 16 7882873
Case #16: 128 65251981
Case #17: 25 10600932
Case #18: 96 39253557
Case #19: 110 61934220
Case #20: 55 30634648
Case #21: 56 26103700
Case #22: 10 1736054
Case #23: 14 7830621
Case #24: 14 6485897
Case #25: 95 50708900
Case #26: 76 33295321
Case #27: 38 19892070
Case #28: 7 4222201
Case #29: 78 37798302
Case #30: 35 17894579
Case #31: 42 19495186
Case #32: 85 37225897
Case #33: 108 54169160
Case #34: 117 57082525
Case #35: 126 64003043
Case #36: 54 29633762
Case #37: 60 28488993
Case #38: 114 58243475
Case #39: 99 49726311
Case #40: 180 98033309
Case #41: 84 41082568
Case #42: 60 33720940
Case #43: 100 48943890
Case #44: 180 88279240
Case #45: 380 191372907
Case #46: 15 8814234
Case #47: 280 141413002
Case #48: 2 808869
Case #49: 9 5919793
Case #50: 99 52474348
my results are correct for all these but still getting wrong answer
Epillion
New poster
Posts: 2 Joined: Thu Oct 08, 2015 11:20 pm
Post
by Epillion Thu Oct 08, 2015 11:29 pm
my code is >>>
Code: Select all
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int arr[150][150];
int sum[150][150];
int Area[10010];
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int t,n,m,K,temp,maxm,area,in,ta,temp1;
cin>>t;
for(int x=1;x<=t;x++){
cin>>n>>m>>K;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&arr[i][j]);
if(i==1) sum[i][j]=arr[i][j];
else sum[i][j]=sum[i-1][j]+arr[i][j];
}
}
maxm=K+1; area=0,ta=0;
for(int i=1;i<=n;i++){
for(int k=1;k<=i;k++){
for(int j=1;j<=m;j++){
if(k==i){
temp=sum[i][j];
in=j+1;
ta=(i)*1;
if(Area[ta]!=0){
if(Area[ta]>temp) Area[ta]=temp;
}else {
Area[ta]=temp;
}
while(in<=m){
temp+=sum[i][in];
in++;
ta=(i)*(in-j);
if(Area[ta]!=0){
if(Area[ta]>temp) Area[ta]=temp;
}
else {
Area[ta]=temp;
}
}
}
else{
temp=sum[i][j]-sum[k][j];
in=j+1;
ta=(i-k);
if(Area[ta]!=0){
if(Area[ta]>temp) Area[ta]=temp;
}
else {
Area[ta]=temp;
}
while(in<=m){
temp1=sum[i][in]-sum[k][in];
temp+=temp1;
in++;
ta=(i-k)*(in-j);
if(Area[ta]!=0){
if(Area[ta]>temp) Area[ta]=temp;
}else {
Area[ta]=temp;
}
// cout<<i<<" "<<k<<" "<<in<<" "<<j<<" "<<ta<<" "<<Area[ta]<<endl;
}
}
}
}
}
maxm=0; area=0;
for(int i=1;i<10010;i++){
if(Area[i]!=0){
if(Area[i]<=K) {area=i;
maxm=Area[i];
}
}
Area[i]=0;
}
printf("Case #%d: %d %d\n",x,area,maxm);
}
}