[HackerEarth] Abdul and apples - P19608

P19608 [HackerEarth] Abdul and apples

普及

题目描述

Abdul and apples

There is a rectangular field of apple trees of size NxM. Abdul is very fond of apples. He wants to collect as many apples as possible. But the owner of the apple field ,Shivam,is super duper smart. He has planted some poisonous trees and he allows Abdul to collect apples on one condition. Abdul can select one square field of apple trees of any size. As some trees are poisonous, they can be said to be negetive apples. Help Abdul maximise the total number of apples. As Abdul is very greedy, he has to pick atleast one tree.

INPUT:
First line will consist of the number of test caes.

The next line will have two integers : the number of rows R and coloums C in the field.

The next R lines will have C integers each representing number of apples on each tree in that row.

OUTPUT:
One integer representing the maximum number of apples possible to collect

Constraints:

1 ≤ R,C ≤100
-10^9 ≤ number of apples ≤10^9

Problem Setter :
Shivam Beri
Problem Tester:
Teja Vojjala

SAMPLE INPUT
1
4 5
1 2 3 4 5
-1 -2 -3 -4 5
2 -1 5 -3 -1
4 5 -10 7 -1

SAMPLE OUTPUT
11

Explanation

The largest sum of square we can choose is :
2 3 4 5
-2 -3 -4 5
-1 5 -3 -1
5 -10 7 -1

which has a sum of 11.

输入格式

见题面

输出格式

见题面

样例输入

100
2 8
1 1 1 1 1 1 1 1
-1 1 -1 1 -1 1 -1 1 

10 3
368 -859 -108 
-11 9 -570 
-615 -97 -95 
-822 -18 -249 
281 -652 182 
-902 -384 -359 
161 20 -95 
-155 6 -870 
-84 590 623 
505 303 -1 

9 3
388 718 -19 
-226 671 287 
-724 852 -559 
204 -415 696 
-475 -412 81 
-21 200 217 
536 -84 -330 
170 370 36 
-549 -367 -524 

7 1
245 
309 
107 
51 
87 
65 
554 

3 1
-545 
354 
575 

9 10
184 -453 -946 -520 112 -340 -165 165 386 -307 
299 -307 484 351 -37 495 216 235 287 -290 
-250 -64 -189 248 -160 -216 517 -209 -148 -150 
246 -141 -467 767 -73 -355 -432 217 -318 -524 
442 727 428 -117 -329 -678 81 503 -637 90 
-866 173 -388 -168 -583 -103 -338 -140 -100 15 
532 647 -324 -130 -115 -71 85 -35 -284 -717 
158 112 -83 -2 -119 181 206 -279 -587 -355 
523 -42 132 104 -113 -443 -237 -336 337 -26 

10 2
85 -293 
-615 -147 
229 -356 
96 -127 
452 150 
-118 567 
-423 63 
-510 -540 
213 763 
190 341 

4 1
95 
-793 
-378 
-414 

3 10
-98 -381 -949 -120 -429 -88 694 350 -64 -836 
-173 -561 100 -598 -49 229 -265 -554 71 -106 
-118 356 -95 85 367 -446 -33 713 -866 -747 

1 6
349 -715 55 796 78 103 

6 8
-299 -97 -60 -473 476 -330 4 86 
-296 -760 -136 -367 -134 -575 89 -167 
187 380 358 277 -381 -457 33 369 
-774 -49 32 609 -135 -593 479 -278 
338 340 269 169 66 508 874 505 
21 544 294 -336 -373 -559 -909 -150 

5 3
88 -431 124 
276 -781 -263 
81 243 566 
-366 -649 -308 
-578 452 -422 

4 5
103 -437 -529 414 581 
-228 0 -320 -266 -254 
309 -377 -273 803 208 
-915 -583 -662 -448 595 

8 10
845 39 -89 -214 -424 -413 83 -326 167 -705 
-7 -66 -74 -111 639 524 -468 -779 223 -367 
242 -57 -711 -472 -560 101 -442 343 -161 249 
-378 -294 -113 586 545 436 -119 -149 -64 107 
838 -167 -132 507 -466 -655 325 -263 -552 278 
-340 65 -193 798 -104 -369 -550 -515 259 306 
-54 -632 246 548 -537 66 -544 106 -190 681 
-247 -191 147 224 -524 564 -509 -11 -408 386 

6 2
53 69 
622 -838 
-54 876 
-180 -256 
-301 -186 
282 529 

7 2
-180 -396 
98 127 
-116 -611 
614 451 
40 28 
540 -36 
-254 -221 

4 5
47 24 104 81 120 
-540 -105 97 227 -266 
341 -459 -371 454 -521 
462 619 -611 968 164 

5 3
372 109 -216 
-373 227 -453 
466 246 68 
-642 707 -98 
-260 291 -76 

3 5
-625 -290 -435 410 -564 
-788 -715 845 267 105 
151 360 -156 578 -814 

5 2
-534 -142 
-657 47 
52 -384 
606 -133 
139 -185 

2 6
10 -210 579 -283 -346 -641 
657 -106 29 -817 -17 -108 

7 9
-284 600 469 -494 -695 -472 -3 844 -291 
460 -221 17 -519 18 943 -210 -185 52 
161 290 -171 136 -246 -888 189 -205 -732 
-308 -521 -96 342 -260 195 -61 -479 -23 
586 -476 429 -420 413 -493 -117 -393 252 
-232 -381 -25 -440 46 87 -336 441 -405 
-363 80 -593 17 15 401 59 -243 550 

2 10
-370 333 -286 -306 40 196 -221 458 50 -176 
-391 -645 332 652 -146 220 -234 6 -102 819 

10 1
122 
428 
-796 
327 
-158 
88 
-5 
358 
-209 
-269 

5 5
647 -14 151 -425 -212 
410 -356 -411 469 233 
-484 -205 -7 685 325 
-282 -639 139 -534 -325 
255 -418 426 61 -45 

4 9
-259 -758 109 -674 -435 -162 -292 109 9 
-923 -587 101 -445 85 676 -137 323 1 
130 -349 17 501 -262 188 198 -80 162 
142 459 -700 68 -17 -233 214 -416 -158 

3 1
124 
439 
142 

2 9
-647 497 132 344 -407 215 2 57 -493 
16 -203 -693 529 54 290 200 473 282 

9 3
-407 31 211 
-55 654 -17 
-550 356 215 
327 -233 -406 
-826 89 164 
-328 -159 691 
-136 -222 202 
387 -147 374 
-55 299 241 

1 5
343 256 -265 399 -339 

9 10
694 -120 123 550 208 419 -71 -290 852 372 
759 -26 -237 122 111 -742 -834 -520 -216 -289 
141 466 -155 305 -544 166 -197 -277 -664 -641 
-274 653 526 -620 500 521 -173 -722 -914 2 
-146 219 -515 -71 415 113 -782 174 -335 -302 
60 -287 83 -443 -547 -724 92 588 -315 261 
-793 -211 83 0 252 500 738 -336 275 486 
601 -532 -68 -425 529 -360 169 44 226 -217 
-96 -438 -483 -233 180 427 -246 -524 -155 430 

3 6
91 -69 15 -434 823 183 
-398 -139 -179 287 -245 -79 
67 248 -351 762 492 143 

2 6
199 197 -106 589 178 -357 
869 95 -643 -134 340 669 

6 2
365 -372 
742 5 
-301 -674 
-259 -875 
-9 602 
-58 -738 

9 8
-272 -586 287 -290 -542 330 -262 64 
-57 -321 -467 -357 -119 -425 548 -293 
271 746 413 5 -350 66 466 -491 
226 276 19 -218 649 -11 304 183 
766 313 513 -788 -302 717 137 728 
-402 116 -394 841 -509 -115 -296 -270 
-737 403 -230 465 -187 -77 -756 595 
428 264 -435 194 -299 -783 263 -307 
289 -447 313 -81 216 -124 -307 -699 

2 3
264 -350 3 
360 -424 -726 

4 1
780 
-686 
-20 
-101 

4 10
945 170 -394 474 -166 -212 299 -42 107 50 
-217 -311 -122 -674 -249 -406 -23 773 127 291 
-55 156 203 -3 -104 240 535 214 453 379 
-6 -191 -236 78 -114 374 -495 408 -62 156 

2 6
115 719 661 -40 -345 -603 
-46 115 -93 -146 185 -19 

6 9
-257 -403 -371 -716 542 189 261 -625 -562 
-421 -684 263 548 -562 173 -550 109 263 
309 -95 -4 -169 7 709 -458 646 -239 
-841 361 -444 -32 110 -71 435 22 -684 
-519 -598 251 840 -618 898 -303 556 -530 
-556 -106 167 -116 247 -579 868 109 -106 

3 8
361 341 254 13 126 -773 -284 495 
71 -169 -59 -371 322 -223 -222 -442 
-353 -484 -115 76 23 -3 -66 -509 

7 6
-431 -156 25 451 -212 -527 
131 -519 250 133 269 876 
328 -560 387 517 451 -379 
-303 211 -306 177 -307 -566 
-473 127 -381 -505 10 -315 
94 124 -533 254 -324 -431 
-241 33 -375 478 -581 -600 

10 9
-298 -221 -261 236 471 395 -327 10 434 
-271 828 -671 -159 103 -260 -42 267 619 
-222 221 640 -350 -251 155 -29 -175 431 
684 -543 538 -127 -603 437 458 457 -133 
191 433 -165 -184 207 -856 356 211 -258 
-372 -690 -272 173 -63 -317 2 -141 -114 
-239 -288 33 -363 -406 516 -712 -475 -562 
69 -87 -288 -163 -362 -837 -133 74 435 
208 132 -79 546 8 325 190 325 -725 
-155 -519 -740 34 479 26 129 741 232 

10 2
-206 149 
-163 -320 
577 427 
-582 423 
-162 645 
-461 125 
-421 119 
724 -316 
5 279 
348 -269 

10 10
407 454 949 -414 -346 270 281 -345 542 104 
-305 -436 374 -374 -585 -141 40 457 -243 -405 
660 215 -43 335 154 -117 339 333 427 384 
285 -855 -137 107 -139 -961 743 25 492 843 
116 -19 184 195 373 -187 -701 242 355 405 
152 -267 -304 -567 -461 -583 -237 102 -257 -261 
860 353 668 -370 709 685 763 -25 558 816 
627 -292 -857 126 79 198 248 -148 381 -571 
-100 141 847 -692 545 31 838 376 88 -353 
360 -107 -86 -57 536 544 -456 68 197 221 

5 10
-819 425 264 -162 501 -694 -217 176 -336 548 
54 273 547 156 -319 -842 -453 125 228 -118 
243 582 -459 -235 74 -528 519 -105 -399 708 
368 -383 -577 850 -469 -349 -399 795 -379 -274 
170 -385 -253 -229 -34 622 441 561 51 65 

5 6
57 -147 569 -111 -483 433 
294 -277 131 162 73 239 
-393 614 -127 58 -275 -311 
-64 -312 73 288 471 678 
-6 46 253 -120 -456 -687 

4 1
674 
62 
509 
-286 

2 3
810 173 -111 
-212 -451 97 

4 8
428 113 290 -2 -442 580 -273 -341 
-272 -144 -293 -299 709 -530 131 129 
-109 62 -597 154 69 -425 -64 478 
-247 516 -17 73 114 -556 516 232 

5 9
624 -477 -346 352 -409 210 355 413 412 
115 -113 -222 -201 -668 490 -237 -96 395 
237 -43 582 -134 -279 -83 43 318 -267 
333 415 68 652 820 -372 82 349 -314 
-255 -367 -48 183 -82 -335 150 -485 46 

8 5
415 -144 325 55 -83 
-414 -239 23 -96 -387 
-273 -670 -313 613 -8 
-902 29 -792 381 37 
-720 113 719 -506 -622 
-450 477 42 -158 322 
505 536 -86 -5 -182 
-543 627 -28 257 443 

6 2
-182 -256 
-294 -946 
586 -226 
484 210 
-256 -93 
-308 -280 

3 2
194 288 
256 -46 
-40 -63 

4 4
61 -223 296 299 
-766 -366 -97 102 
435 -177 -149 125 
-795 198 -400 -582 

6 2
-408 572 
-260 -746 
462 121 
333 7 
-615 -26 
-252 67 

3 7
38 81 -329 389 390 -425 -762 
-432 931 845 -81 369 -24 20 
-252 -39 235 131 211 -488 240 

6 7
97 303 91 -378 274 -258 586 
-452 -599 798 -273 -363 12 -289 
161 57 -8 803 -389 -175 -489 
-120 546 -41 424 209 -5 312 
-105 292 -399 -120 561 -84 -326 
-907 -71 176 314 50 628 897 

9 9
-42 -210 270 -511 -480 -843 -333 481 243 
461 732 825 -129 -94 -491 568 -453 -127 
838 0 345 -458 -674 406 410 525 135 
192 -819 -277 -288 -71 234 334 -334 21 
-260 256 -121 611 -398 16 -90 -459 -316 
-599 -192 -591 419 -225 141 -149 32 -673 
-211 359 -157 -689 -165 -53 101 -335 116 
-183 517 -189 -572 -432 -739 185 -303 -229 
101 496 -371 191 558 420 -561 -328 -184 

9 9
568 -269 -285 278 -207 838 -407 -164 -276 
306 -567 354 750 -258 -844 388 386 542 
395 -770 144 567 478 149 32 269 117 
-364 42 44 554 -278 185 -247 -524 449 
363 145 628 -881 -287 -234 -357 73 253 
465 273 -302 141 290 150 -248 -293 1 
-301 222 104 -264 -174 258 260 -91 -247 
-202 286 -436 553 -798 -15 48 220 640 
20 592 -110 -274 -272 -168 -318 -858 -11 

5 1
69 
-425 
413 
911 
734 

6 7
-242 -608 538 -508 -271 27 -4 
-367 705 -261 -740 359 -315 389 
33 -283 324 -25 29 -714 -184 
68 40 -881 -237 322 699 -477 
-22 67 85 305 207 662 721 
316 -444 246 -363 -608 -496 159 

2 1
-254 
-283 

2 1
339 
-168 

8 7
179 -475 -36 158 -138 627 260 
-12 60 -187 -811 -36 307 -46 
578 136 -193 532 168 381 -443 
795 -292 518 -527 199 -277 -430 
62 338 303 -285 467 -229 -33 
393 596 -133 -33 35 556 -44 
-69 -676 169 76 -592 -12 326 
-172 258 -159 -655 54 -19 39 

3 6
753 -657 -732 2 -2 -156 
466 -431 -306 39 392 727 
-959 -594 432 385 -96 38 

7 8
187 -350 274 212 483 -927 560 348 
-164 229 -157 -99 -149 575 -31 299 
59 -945 -459 470 -324 686 84 260 
-57 35 -325 -224 195 -32 -130 -206 
435 -50 -37 -509 -532 428 -716 -302 
-358 -253 -538 169 443 443 656 688 
74 13 107 710 -645 -94 78 406 

10 5
435 244 367 330 -306 
252 881 215 406 255 
270 314 515 100 -394 
222 -348 470 -94 840 
667 -5 -312 581 536 
-138 100 -200 -948 -3 
468 542 359 675 -198 
-99 -447 774 -98 -167 
756 401 -233 -19 31 
289 -592 -738 298 36 

10 7
-78 24 -652 -209 116 -104 286 
-145 -495 -254 281 552 534 -376 
-561 -158 -209 161 261 -426 -177 
-498 184 -108 -267 136 -245 -259 
-316 38 -211 346 338 59 -230 
18 -247 62 164 655 -32 -82 
-94 64 58 119 -601 855 -660 
-242 73 460 259 78 851 94 
530 -10 -293 16 407 -9 -404 
177 894 -222 -148 90 563 231 

1 3
-52 683 727 

9 9
110 -965 426 -43 138 -33 -113 266 279 
-93 450 -276 -642 -363 -15 120 -431 -881 
-27 -71 270 239 262 -580 568 -454 142 
414 181 381 100 -525 96 -846 130 -257 
289 -289 94 200 286 -623 -108 282 59 
-452 818 -31 -195 -492 -128 114 152 254 
288 832 170 310 -469 282 36 554 -337 
-629 360 -667 120 -73 -164 -12 -77 163 
-261 -333 602 77 179 -240 -122 -73 -401 

7 2
504 -448 
-42 -487 
-137 914 
-79 -145 
363 -261 
-272 -68 
110 -97 

3 9
261 441 -628 381 -90 147 284 893 619 
-450 356 170 -304 561 -261 590 228 -12 
179 682 666 298 -279 309 22 -391 -270 

5 10
-452 604 -183 118 -142 -16 -218 451 -411 -454 
385 -229 -233 -298 -94 709 -73 328 308 -582 
-600 -554 395 -542 823 370 380 359 113 4 
-427 111 -175 301 320 124 813 101 484 414 
369 429 59 -905 185 -668 739 13 -822 36 

10 10
-580 233 -75 296 48 329 624 -50 -211 -104 
516 517 -302 331 -173 -380 432 276 606 184 
798 129 -428 -406 -577 -129 103 -126 -773 -589 
-619 227 -231 575 -455 -182 51 -168 -398 19 
160 213 114 115 -390 489 -352 -307 -16 -296 
620 -488 436 751 -246 -114 477 203 -482 94 
101 119 -476 458 340 186 -575 -407 -469 -91 
82 413 -40 599 -468 76 -170 -435 152 444 
118 18 -504 102 158 -422 283 -8 -24 179 
-686 415 13 570 -377 -185 236 449 -617 21 

1 2
-562 606 

2 5
-91 -642 -493 493 40 
285 -498 151 -296 136 

8 1
352 
29 
-278 
-62 
-34 
-752 
105 
460 

5 10
-519 -279 -161 504 -367 -715 -694 734 -287 -699 
184 -222 -201 -438 471 -391 151 683 -143 -282 
-848 -21 469 -104 345 63 -275 -62 13 -180 
155 424 -118 -164 563 -729 -365 384 242 -332 
-457 -392 662 -69 -114 -21 -305 -327 -85 -50 

2 8
-109 100 3 -496 668 -61 -520 495 
-271 -474 -141 134 -89 201 -122 262 

8 2
114 -338 
-153 687 
-125 -528 
282 242 
-341 -318 
-618 240 
476 118 
525 341 

10 6
-871 575 -234 -360 -449 485 
398 813 -9 -866 100 116 
-356 -211 491 -290 578 -64 
191 -229 -762 -182 70 -396 
-27 -735 -213 -719 146 -609 
-420 -780 -726 731 -107 747 
-76 240 -160 -408 57 -876 
238 76 -440 -158 -104 63 
50 631 -419 65 784 -649 
471 282 388 544 404 -684 

10 6
-99 -488 -96 594 325 -88 
92 708 304 -192 658 360 
-161 109 762 -345 -190 675 
45 0 -485 255 52 -8 
-343 -195 414 -231 -506 -199 
-275 2 753 -119 576 311 
11 456 504 -517 -548 428 
496 435 246 -504 -611 892 
-143 802 -704 -421 172 -154 
-437 -28 745 -105 22 -117 

8 4
-237 -279 590 -199 
-106 413 575 -162 
-306 283 -339 -2 
61 593 -413 546 
882 404 302 -324 
-513 688 243 -510 
-246 -337 70 -307 
567 595 34 -337 

4 2
755 -282 
511 457 
-480 -690 
-842 25 

5 5
589 -283 -236 -486 121 
244 583 -48 77 892 
168 93 -320 285 -86 
-815 396 743 411 -610 
294 355 -481 274 -44 

2 10
-614 -233 -31 92 -152 -42 378 617 -409 206 
108 307 82 18 481 -799 -410 -81 273 444 

6 1
-576 
-633 
205 
21 
429 
-800 

5 9
344 -42 -273 -215 278 -204 -63 222 -740 
-249 -92 -454 -97 -536 851 -530 162 279 
779 -4 426 -498 248 17 452 -21 791 
-608 452 -799 -178 98 335 254 830 670 
-583 245 206 -98 -34 -67 -477 -255 60 

5 8
351 166 607 -45 -607 -333 -349 18 
-476 -109 627 148 -451 -455 -168 -38 
929 -915 738 76 459 -680 472 -12 
393 -750 -635 337 334 -14 119 -373 
217 -332 -567 723 -108 -89 -528 339 

6 3
418 121 -6 
-712 -26 216 
-32 -639 -715 
-126 -825 109 
198 -581 663 
720 -918 -448 

2 8
-8 -645 -98 -189 216 -57 656 264 
-532 -113 98 -664 123 -819 563 348 

10 5
224 -570 12 -347 -334 
456 463 43 -70 469 
143 -428 289 233 -707 
-162 -144 2 49 -813 
-578 59 27 386 222 
-494 -117 590 -233 -878 
-492 -685 304 -167 -188 
-657 196 -198 388 223 
443 -174 -699 174 -316 
503 -257 -247 34 -221 

5 3
-333 -621 -572 
226 -397 377 
-634 -149 37 
60 -106 -696 
-403 525 -520 

1 4
38 -621 -839 629 

10 10
-104 -531 8 -92 389 -471 438 312 433 521 
-453 425 -452 474 7 -614 -254 -576 417 -78 
-122 583 338 307 430 -35 -293 -262 183 549 
-596 373 -549 70 439 -769 -14 481 -326 -67 
-404 356 -447 68 -173 517 120 -537 -514 -882 
-85 -68 342 -179 369 -977 -204 415 -686 516 
-192 -249 393 32 -734 602 -301 -169 -172 -779 
284 423 534 -659 402 -405 22 340 478 -672 
-8 -343 -478 450 35 472 -236 159 631 -651 
-529 -94 -778 550 273 687 272 -724 -339 -675 

3 8
151 98 -34 -445 -167 -648 615 -664 
-574 -239 -754 -272 18 -426 -298 77 
-527 53 60 16 897 664 -19 -303 

5 10
31 532 -375 531 -36 470 423 -331 645 -630 
438 -108 -340 -103 -36 323 186 177 -453 -361 
-522 71 284 -547 602 -930 725 114 150 277 
-335 697 -190 597 -281 -121 -753 -114 -119 -823 
293 -717 -273 107 349 -256 -353 513 199 -383 

5 4
498 340 780 312 
48 173 70 -464 
359 -47 -134 -370 
-385 -406 76 716 
224 -385 -205 224 

5 4
339 48 195 303 
-94 459 119 86 
482 63 387 -199 
-433 215 208 655 
364 -294 -9 -310

样例输出

题目信息

时间限制	2000 ms
内存限制	256 MB
难度	普及
提交数	0
通过数	0
通过率	0.0%

登录后 AI 解题查看题解登录后提交