Submitted 4 years 10 months 1 day ago
Tue Jan 14 22:27:36 CST 2020
Judger: ZJS
Dataset Version: v0
155 ms /
63504 KB
Final
100
Problem: lss1.trifang
Language: GNU C++ 11
2 8 1 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827
29358
29358
"29358"
7 2 1 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912
21726
21726
"21726"
8 10 4 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 32757 20037 12859 8723 9741 27529 778 12316 3035 22190 1842 288 30106 9040 8942 19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 1262<...>
336998
336998
"336998"
3 7 1 9161 18636 22355 24767 23655 15574 4031 12052 27350 1150 16941 21724 13966 3430 31107 30191 18007 11337 15457 12287 27753
31107
31107
"31107"
4 6 2 32209 9758 24221 18588 6422 24946 27506 13030 16413 29168 900 32591 18762 1655 17410 6359 27624 20537 21548 6483 27595 4041 3602 24350
71074
71074
"71074"
2 7 1 11020 4596 24021 27348 23199 19668 24484 8281 4734 53 1999 26418 27938 6900
27938
27938
"27938"
9 8 3 3728 14893 24648 22483 17807 2421 14310 6617 22813 9514 14309 7616 18935 17451 20600 5249 16519 31556 22798 30303 6224 11008 5844 32609 14989 32702 3195 20485 3093 14343 30523 1587 29314 9503 7448 25200 13458 6618 20580 19796 14798 15281 1<...>
181079
181079
"181079"
5 7 3 31998 10322 18651 10021 5699 3557 28476 27892 24389 5075 10712 2600 2510 21003 26869 17861 14688 13401 9789 15255 16423 5002 10585 24182 10285 27088 31426 28617 23757 9832 30932 4169 2154 25721 17189
173232
173232
"173232"
7 10 1 28692 21425 10555 3434 16549 7441 9512 30145 18060 21718 3753 16139 12423 16279 25996 16687 12529 22549 17437 19866 12949 193 23195 3297 20416 28286 16105 24488 16282 12455 25734 18114 11701 31316 20671 5786 12263 4313 24355 31185 20053 912<...>
31316
31316
"31316"
10 7 4 4474 28022 2168 14018 18787 9905 17958 7391 10202 3625 26477 4414 9314 25824 29334 25874 24372 20159 11833 28070 7487 28297 7518 8177 17773 32270 1763 2668 17192 13985 3102 8480 29213 7627 4802 4099 30527 2625 1543 1924 11023 29972 1306<...>
257587
257587
"257587"
1 5 1 21624 28019 2125 26576 21694
28019
28019
"28019"
9 3 2 22466 4678 22593 23851 25484 1018 28464 21119 23152 2800 18087 31060 1926 9010 4757 32170 20315 9576 30227 12043 22758 7164 5109 7882 17086 29565 3487
93154
93154
"93154"
8 5 2 25627 5629 31928 25423 28520 6902 14962 123 24596 3737 13261 10195 32525 1264 8260 6202 8116 5030 20326 29011 30771 6411 25547 21153 21520 29790 14924 30188 21763 4940 20851 18662 13829 30900 17713 18958 17578 8365 13007 11477
104004
104004
"104004"
1 9 1 2303 12760 19357 2324 6477 5108 21113 14887 19801
21113
21113
"21113"
1 1 1 12993
12993
12993
"12993"
5 6 1 31111 28704 12835 32356 6072 29350 18823 14485 20556 23216 1626 9357 8526 13357 29337 23271 23869 29361 12896 13022 29617 10112 12717 18696 11585 24041 24423 24129 24229 4565
32356
32356
"32356"
10 3 1 29855 12053 16962 3584 29734 6654 16972 21457 14369 22532 2963 2607 2483 911 11635 10067 22848 4675 12938 2223 22142 23754 6511 22741 20175 21459 17825 3221 17870 1626
29855
29855
"29855"
5 6 2 23850 17398 22279 22701 12193 12734 1637 26534 5556 1993 10176 25705 6962 10548 15881 300 14413 16641 19855 24855 13142 11462 27611 30877 20424 32678 1752 18443 28296 12673
87936
87936
"87936"
1 4 1 20072 12818 610 1017
20072
20072
"20072"
3 3 2 13169 23831 20040 26488 28685 19090 19497 2589 25990
81593
81593
"81593"
6 4 1 18651 26740 22044 11258 335 8759 11192 7605 25264 12181 28503 3829 23775 20608 29292 5997 17549 29556 25561 31627 6467 29541 26129 31240
31627
31627
"31627"
4 5 2 6077 20215 8683 8213 23992 25824 5601 23392 15759 2670 26428 28027 4084 10075 18786 15498 24970 6287 23847 32604
85026
85026
"85026"
4 2 2 5706 2363 9010 22171 27489 18240 12164 25542
0
0
"0"
10 4 4 6704 31818 9232 750 25205 4975 1539 303 11422 21098 11247 13584 13648 2971 17864 22913 11075 21545 28712 17546 18678 1769 15262 8519 13985 28289 15944 2865 18540 23245 25508 28318 27870 9601 28323 21132 24472 27152 25087 28570
0
0
"0"
4 2 2 14423 3527 11600 26969 14015 5565 28 21543
0
0
"0"
8 9 4 12637 22409 26463 5049 4681 1588 11342 608 32060 21221 1758 29954 20888 14146 690 7949 12843 21430 25620 748 27067 4536 20783 18035 32226 15185 7038 9853 25629 11224 15748 19923 3359 32257 24766 4944 14955 23318 32726 25411 21025 20355 31001<...>
313359
313359
"313359"
3 7 1 20482 1355 21015 1131 18230 17841 14625 2011 32637 4186 19690 1650 5662 21634 10893 10353 21416 13452 14008 7262 22233
32637
32637
"32637"
5 4 3 26303 14256 148 11124 12317 4213 27109 24028 29200 21080 21318 16858 24050 24155 31361 15264 11903 3676 29643 26909
0
0
"0"
3 2 2 24948 1282 13653 30674 2220 5402
0
0
"0"
4 2 2 3878 20259 19008 22619 23971 30003 21945 9781
0
0
"0"
5 3 1 25313 6698 5589 12722 5938 19037 6410 31461 6234 12508 9961 3959 6493 1515 25269
31461
31461
"31461"
8 10 3 14700 13971 26264 15117 16215 24555 7815 18330 3039 30212 29288 28082 1954 16085 20710 24484 24774 8380 29815 25951 6541 18115 1679 17110 25898 23073 788 23977 18132 29956 28689 26113 10008 12941 15790 1723 21363 28 25184 24778 7200 5071 18<...>
164676
164676
"164676"
5 10 1 17902 29873 17124 23941 32745 31762 28423 27531 4806 12268 9318 5602 31907 24307 23481 1012 21136 26630 24114 26809 4084 23556 12290 21293 29996 29152 1054 25345 14708 248 7491 13712 5131 30114 16439 7958 24722 29704 6995 1052 25269 7479 18<...>
32745
32745
"32745"
3 4 1 12022 1146 18392 13037 3925 10647 29458 6602 30807 4098 27830 29292
30807
30807
"30807"
1 9 1 18352 20448 13882 540 28315 4575 8762 9567 22336
28315
28315
"28315"
8 9 2 25828 13851 26816 24230 4449 16925 658 229 24520 10940 29560 15147 25162 1655 20675 792 22361 31754 16398 23146 8714 26946 21188 19569 8638 27663 15075 24515 11521 475 15615 20528 13234 12570 905 9464 19557 28962 14161 30524 12549 17469 330 <...>
110467
110467
"110467"
3 5 1 23826 28396 7572 6249 14640 29174 18819 943 32611 1941 20289 8419 5565 3805 7585
32611
32611
"32611"
7 1 1 2609 11064 9166 16893 16074 13509 30300
30300
30300
"30300"
6 4 2 13161 31172 17968 27358 26031 26268 19426 28510 10422 30774 8779 30910 23552 4182 25391 15495 5764 874 1364 14902 28255 4460 474 6972
114245
114245
"114245"
2 3 1 21577 9789 25605 30195 27594 7950
30195
30195
"30195"
4 5 2 1012 11672 23439 13428 5912 9762 5967 24408 4415 1908 17223 11759 26434 5204 29486 4319 958 5945 26806 8166
80248
80248
"80248"
1 8 1 21787 28532 30556 30974 3447 5021 18283 26222
30974
30974
"30974"
2 7 1 26948 12723 17982 22018 14776 9220 31111 32182 23856 19490 8925 4324 6486 19677
32182
32182
"32182"
10 4 3 15677 22668 31068 21991 32196 7783 16828 7727 29426 15871 10697 17612 18703 11027 11408 5545 9508 7185 30238 24237 26443 21313 22501 8850 25128 2111 23650 28149 11192 1454 15869 681 27465 20267 17713 19793 18634 25472 20972 22830 <...>
0
0
"0"
2 3 1 13877 25770 702 14364 1381 16590
25770
25770
"25770"
4 8 2 32179 16595 20169 2327 12042 31310 28182 11058 7926 9487 1670 32528 5651 2258 7213 9860 25783 21286 2742 8610 4472 7128 18434 5841 20718 3503 14867 24865 10938 1881 9257 22750
68745
68745
"68745"
5 9 1 2661 26063 32756 20807 20278 19489 19435 6365 32075 7586 1386 7833 8360 13330 26048 8928 29492 12433 23840 6766 1735 19810 11599 11837 21892 31982 7328 29352 11369 31244 21794 6608 9252 11647 17432 9535 7208 3264 3497 23243 27649 22015 26841<...>
32756
32756
"32756"
3 9 2 19851 24474 28633 29891 27200 19854 9990 25697 4919 17780 22578 12931 32544 3340 13487 899 22525 8483 5538 7492 6193 28252 25011 1560 15834 1840 31497
103618
103618
"103618"
6 10 2 18805 28791 13392 13210 13549 21578 26979 30971 9277 73 20193 1620 21497 13826 31276 19790 6582 13578 11159 20418 26489 159 3449 12924 9072 10380 27008 27967 10208 6477 18503 15370 32607 14196 12074 13722 12611 19019 28761 11056 12890 31163<...>
101068
101068
"101068"
5 1 1 17006 8670 241 18882 25249
25249
25249
"25249"
42 68 14 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 1514<...>
3489234
3489234
"3489234"
93 65 26 18866 14693 30664 23775 13000 12212 21100 7551 25476 6379 10943 17877 3789 361 11385 8272 11434 15144 29561 25563 14504 12946 23888 20308 12157 1430 5123 6464 4074 4346 13837 1981 25318 26611 16292 17591 3832 27123 6461 16991 31461 27330 28498 17<...>
11543750
11543750
"11543750"
49 30 16 32633 21367 12637 27323 25445 29003 27994 8086 3734 1452 5275 2541 1925 27201 4855 15304 22378 1391 28433 13260 2725 22826 28125 690 4189 29707 3935 25847 15719 30883 18614 9428 30313 12048 8026 22640 17727 21709 2466 20565 23965 7887 14473 189<...>
0
0
"0"
97 35 14 32172 11048 23 22291 18166 30261 4981 941 16461 29443 12245 3696 14229 8373 23900 3650 6703 24828 14731 8941 24523 1942 22710 8388 6013 788 23479 8073 19220 737 3555 28814 11431 16000 7997 16411 17008 16917 20202 26128 1245 25639 6629 10699 893<...>
3441503
3441503
"3441503"
40 77 8 27037 21757 13570 12020 12751 23324 32199 23935 15580 25132 11061 23452 17560 1277 21486 28717 5101 17446 4668 14376 20617 30956 15201 20634 3284 28517 8488 25068 13861 27613 4544 28773 13109 8056 2506 5617 18132 20505 19633 2337 2778 14211 22330 <...>
1312401
1312401
"1312401"
81 90 6 15820 16055 29841 11107 14143 5735 30121 4834 13992 5049 13131 16499 25812 9687 25420 18595 8684 4823 16311 6240 5623 22065 15219 26379 10912 17271 27167 3790 21049 16704 8001 16176 16385 12390 2208 15846 30114 21361 18414 10732 18942 19026 20394 <...>
802000
802000
"802000"
69 53 24 7588 21949 14021 3622 5452 8682 30728 6968 13500 17380 5251 13518 14376 29016 27710 30619 21250 13123 14927 28721 26153 4953 7339 21374 26206 14504 20028 8342 1783 14201 18228 4019 31959 6263 14240 29305 28061 23315 4160 27007 24348 30502 3478 48<...>
9734261
9734261
"9734261"
56 54 6 22452 29153 16667 6553 8011 31655 3435 22019 27459 25689 31941 24039 23298 25368 27094 24845 24515 25216 6614 16545 909 31699 23318 894 7265 11603 29144 24492 16312 20463 18276 32038 2605 4130 3928 21985 3958 28185 22336 22283 1688 2324 13414 1012<...>
747267
747267
"747267"
3 9 2 17913 1451 6916 30945 29695 14644 10200 15192 21502 31815 10670 30696 28254 31293 4300 18122 32573 12361 4331 19175 9143 30122 22681 7078 27749 21541 22492
120017
120017
"120017"
59 12 8 23064 13791 535 9335 30514 9374 29167 30194 8182 20975 30057 17018 18870 27110 9241 12264 32052 9042 9831 7826 19651 27978 31959 25465 30120 6920 19597 29379 12486 507 21776 3691 30331 15895 29518 19767 14789 4208 21984 3562 24233 3079 18064<...>
0
0
"0"
42 468 14 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 151<...>
3628190
3628190
"3628190"
396 779 34 18689 32264 15410 19108 25202 14285 28381 15349 30402 13648 27958 27012 19594 4058 25652 8696 14115 20334 30106 4760 14090 6562 31612 3259 31113 17070 9471 16255 31636 29891 20576 14782 21490 24990 17976 18494 26781 12892 14846 1064 4970 10640 <...>
20373162
20373162
"20373162"
310 681 61 2959 31511 24294 7351 26164 1245 27572 4648 25487 24577 7142 2807 29239 2322 24800 15814 3539 28262 2988 9034 18641 8964 17481 24659 7771 14528 2885 4358 8326 1448 31118 22893 22221 22687 12933 24371 24767 24904 15444 4264 12532 20262 12929 238<...>
63173817
63173817
"63173817"
725 442 311 11037 8735 2990 22511 14925 22528 8687 18110 19826 8996 18706 29929 8305 14565 26071 26051 21666 29514 28665 24750 18485 23258 9392 27020 31950 690 17018 7543 20851 27350 12827 18354 5032 23749 16610 17119 11224 30288 20527 31346 26871 22187 7<...>
0
0
"0"
680 806 137 7047 15116 23629 17933 31088 16847 25544 25743 26201 27661 13162 9945 14117 12522 17490 17893 5111 24269 5853 15847 20551 25374 27490 29741 2358 16206 29472 29770 32286 20248 3444 2163 22382 17415 25936 12585 20405 31289 744 16409 29436 2658 9<...>
312875167
312875167
"312875167"
519 445 244 15371 22805 3330 14028 29864 9626 16038 28038 14792 13712 7937 4352 8697 9313 32420 1816 13552 28411 27282 23891 27761 295 21575 24783 15471 11542 31481 29305 26229 16701 31261 27519 7236 12388 8493 9737 13758 32761 30889 32292 32258 28841 623<...>
0
0
"0"
220 547 66 29645 1899 26258 19526 24096 14943 8238 12103 28637 5672 5645 32060 5510 7125 12627 30155 24314 28502 19323 31886 4411 12851 28225 26983 1396 30334 19135 13076 31035 24070 11222 10243 13331 14797 26575 10599 9781 15804 5442 7307 25744 7318 1847<...>
73636690
73636690
"73636690"
926 831 443 19879 15020 4335 11556 22205 3510 555 31389 27140 17160 28165 2016 29453 11194 26052 21346 8069 923 10124 3596 23233 20085 5774 667 10139 6802 891 3143 19581 19582 22846 24738 1467 22543 490 12484 12838 2723 6129 26021 11742 19113 14232 31690 <...>
0
0
"0"
592 488 75 2113 24437 2558 7210 2495 2148 23352 18340 8214 6219 23291 16690 13100 8459 14068 5592 6593 25843 5256 20605 501 11572 23922 9209 17163 25748 16302 31599 31852 19046 25750 25821 9711 20921 9036 2545 30039 208 12887 11039 15646 25810 7313 20720 <...>
95166566
95166566
"95166566"
782 902 36 2066 26208 31091 15158 13869 12534 14399 19306 9990 25675 19938 14297 9450 16199 25652 3920 7814 25779 1644 5490 22781 5369 988 27297 2104 13611 27355 27426 16766 18247 12290 2427 31812 14266 21915 10272 5446 9250 10070 13903 2006 32600 24126 5<...>
22896678
22896678
"22896678"
42 468 14 0 15724 0 0 0 0 28145 16827 491 11942 5436 14604 0 292 0 18716 0 5447 0 11538 19912 26299 9894 23811 0 17673 0 7711 6868 27644 0 20037 8723 27529 0 0 22190 0 0 0 0 0 0 0 0 15890 24370 0 0 24393 0 12623 0 0 0 0 0 0 26308 0 24626 5537 0 0 0 16541 <...>
2283849
2283849
"2283849"
406 441 27 0 17464 0 0 9224 0 755 0 0 0 28746 0 0 0 31952 19923 19100 14712 10162 26295 0 11882 0 14464 10609 0 0 0 0 19956 0 0 0 0 10346 15420 0 25048 10071 16764 32663 8217 3934 18831 0 0 28706 20759 0 0 0 12489 20747 31545 19487 9765 30811 0 0 0 10516 <...>
7162015
7162015
"7162015"
449 643 150 18456 0 0 0 0 13564 6151 11859 0 3806 3563 6188 0 23188 0 0 0 26475 0 21498 0 0 0 0 10292 10618 17062 29479 0 31013 5785 0 0 0 30541 10837 0 0 0 0 5550 15813 4712 0 0 8555 7805 0 0 0 20782 18161 25127 32204 0 25759 7307 0 9019 32335 0 12441 0 <...>
189512610
189512610
"189512610"
409 866 97 0 8896 29704 0 18966 0 0 0 0 0 0 11277 7605 1039 0 0 0 0 32087 31070 0 0 14063 0 30348 0 0 0 0 0 0 16951 13405 18924 29864 3114 0 0 30022 0 0 27623 0 11311 29269 0 0 0 5841 1801 2016 28061 0 0 0 0 0 0 0 0 0 21699 16944 0 0 26058 0 14402 6001 43<...>
79749042
79749042
"79749042"
257 703 22 0 9758 0 0 32129 0 18392 0 26121 0 0 0 0 27001 0 0 2435 20766 22048 30858 17162 13540 97 2416 0 0 30365 20176 11226 0 31700 0 0 0 13819 10485 3252 0 4157 20282 13309 21037 0 0 0 5855 0 13255 0 0 0 18871 0 12591 0 23127 2299 29693 17579 1457 146<...>
4807944
4807944
"4807944"
293 849 133 6736 0 0 0 12976 21295 0 25102 477 22813 0 18820 0 0 0 0 24522 0 16649 29141 20274 0 1414 0 0 0 0 21009 5605 31907 0 0 5141 0 17589 0 10996 0 0 8522 3761 31376 0 0 19326 0 18955 0 9012 31118 31300 4388 0 6013 7886 0 0 23003 28686 0 13120 15119<...>
148241677
148241677
"148241677"
726 776 149 4628 1635 0 7409 20067 13741 31345 31851 3150 0 0 0 0 8822 0 0 27273 0 24953 0 28687 0 0 17009 30758 0 0 29049 0 0 0 10690 0 13381 0 0 24090 16862 25191 0 2082 0 25768 0 0 20520 22957 0 0 0 0 4288 21788 18881 32454 1877 0 0 11537 0 0 21770 0 0<...>
186936922
186936922
"186936922"
831 631 137 9512 7650 6264 0 17749 0 14738 0 0 19441 0 0 6378 0 0 0 0 10668 16521 0 27519 15469 0 20549 20968 29432 17416 6054 7517 0 12653 3887 4615 2940 0 0 1338 0 6783 0 15529 0 0 605 6055 10112 16675 0 2944 1059 6690 24830 327 0 22366 0 0 0 0 30236 18<...>
158244252
158244252
"158244252"
718 366 52 0 26357 30763 0 0 0 31871 23356 16459 0 0 4698 0 15729 0 0 15130 0 0 0 0 25199 2601 15817 31092 26234 17466 0 15178 0 12058 0 31613 0 11616 134 24425 5316 27665 0 5775 0 3325 12450 24634 0 13243 9017 26079 0 0 27620 0 0 0 0 0 0 0 0 29368 10504 <...>
24478479
24478479
"24478479"
679 968 316 12512 0 0 0 23536 0 0 16360 0 0 7920 0 20860 20718 13506 0 0 8072 29699 0 21898 0 18910 0 0 0 378 0 0 0 27937 7998 0 30558 0 0 0 0 15532 0 0 0 13995 0 1468 32022 23072 26588 0 10793 0 30340 0 0 21446 11807 0 29526 0 0 0 0 0 19322 4735 8573 136<...>
824422692
824422692
"824422692"
42 468 21 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 466<...>
7717157
7717157
"7717157"
125 396 63 3778 16467 18689 32264 15410 19108 25202 14285 28381 15349 30402 13648 27958 27012 19594 4058 25652 8696 14115 20334 30106 4760 14090 6562 31612 3259 31113 17070 9471 16255 31636 29891 20576 14782 21490 24990 17976 18494 26781 12892 14846 1064 <...>
66099588
66099588
"66099588"
165 479 83 16377 13275 16969 23153 658 18321 21214 10953 23428 28170 7622 6236 3113 17225 28353 8316 15061 14687 117 8392 26112 20212 10418 25178 4775 5155 6650 25922 14831 29067 24129 51 14860 26018 28401 10365 20065 11341 3633 30267 21224 1198 17767 145<...>
114641083
114641083
"114641083"
/*
Though leaves are many, the root is one;
Through all the lying days of my youth
I swayed my leaves and flowers in the sun,
Now may I wither into the truth.
- William Butler Yeats
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
#include <bitset>
//#include <windows.h> //Should be deleted when using AtCoder&POJ
using namespace std;
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
#define dbg if(false)
/**==Info==
*Program:1
*Problem:Rhombus
*Date:2019-12-30
*Algorithm:My rubbish prefix sum and violence
*Status:Unknown*/
bool debug=false;
ll n,m,k;
ll a[1005][1005];
ll tri[4][1005][1005];
ll colsum[1005][1005],rowsum[1005][1005];
int dsuid[1005][1005],dsuind[1005][1005];
ll dsusum[2005][2005];
int dsdid[1005][1005],dsdind[1005][1005];
ll dsdsum[2005][2005];
ll f[1005][1005];
int dsuic,dsdic;
const int L=0,R=1;
void runDsu(int x,int y){
int cnt=0;
while(true){
dsuid[x][y]=dsuic;
dsuind[x][y]=cnt;
dsusum[dsuic][cnt]=(cnt==0?0:dsusum[dsuic][cnt-1])+a[x][y];
cnt++;
x--;y++;
if(x<0 || y>=m){
break;
}
}
dsuic++;
}
void runDsd(int x,int y){
int cnt=0;
while(true){
dsdid[x][y]=dsdic;
dsdind[x][y]=cnt;
dsdsum[dsdic][cnt]=(cnt==0?0:dsdsum[dsdic][cnt-1])+a[x][y];
cnt++;
x++;y++;
if(x>=n || y>=m){
break;
}
}
dsdic++;
}
inline ll getCS(int col,int st,int ed){
if(st>ed){
swap(st,ed);
}
return colsum[col][ed]-(st==0?0:colsum[col][st-1]);
}
//inline int getDSUId(int x,int y){
// return dsuid[x][y];
//}
//
//inline int getDSUInd(int x,int y){
// return dsuind[x][y];
//}
//
//inline int getDSDId(int x,int y){
// return dsdid[x][y];
//}
//
//inline int getDSDInd(int x,int y){
// return dsdind[x][y];
//}
inline ll getDSU(int id,int st,int ed){
if(st>ed){
swap(st,ed);
}
return dsusum[id][ed]-(st==0?0:dsusum[id][st-1]);
}
inline ll getDSD(int id,int st,int ed){
if(st>ed){
swap(st,ed);
}
return dsdsum[id][ed]-(st==0?0:dsdsum[id][st-1]);
}
inline ll getDSU(int x1,int y1,int x2,int y2){
dbg cout<<"DSU="<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dsuid[x1][y1]<<" "<<dsuid[x2][y2]<<endl;
assert(dsuid[x1][y1]==dsuid[x2][y2]);
return getDSU(dsuid[x1][y1],dsuind[x1][y1],dsuind[x2][y2]);
}
inline ll getDSD(int x1,int y1,int x2,int y2){
dbg cout<<"DSD="<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dsdid[x1][y1]<<" "<<dsdid[x2][y2]<<endl;
assert(dsdid[x1][y1]==dsdid[x2][y2]);
return getDSD(dsdid[x1][y1],dsdind[x1][y1],dsdind[x2][y2]);
}
inline ll getRS(int rownum,int l,int r){
if(l>r){
swap(l,r);
}
return rowsum[rownum][r]-(l==0?0:rowsum[rownum][l-1]);
}
void proceedL(){
for(int i=k-1;i<=n-k;i++){
int up=k-1;
for(int j=0;j<k;j++){
tri[L][i][k-1]+=getCS(k-1-j,i-up,i+up);
up--;
}
}
for(int i=k-1;i<=n-k;i++){
dbg cout<<"Doing line "<<i<<endl;
for(int j=k;j<=m-k;j++){
dbg cout<<"Solving for column "<<j<<endl;
ll p1=tri[L][i][j-1];
ll p2=getCS(j,i-k+1,i+k-1);
ll p3=getDSU(i,j-k,i-k+1,j-1);
ll p4=getDSD(i,j-k,i+k-1,j-1);
ll p5=a[i][j-k];
dbg cout<<i<<" "<<j<<" p="<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<endl;
tri[L][i][j]=p1+p2-p3-p4+p5;
}
}
// dbg{
ll mx=0;
for(int i=k-1;i<=n-k;i++){
for(int j=k-1;j<=m-k;j++){
mx=max(mx,tri[L][i][j]);
}
}
cout<<mx<<endl;
exit(0);
// }
}
void proceedR(){
for(int i=k-1;i<=n-k;i++){
int up=k-1;
for(int j=0;j<k;j++){
tri[R][i][k-1]+=getCS(k-1+j,i-up,i+up);
up--;
}
}
for(int i=k-1;i<=n-k;i++){
dbg cout<<"Doing line "<<i<<endl;
for(int j=k;j<=m-k;j++){
dbg cout<<"Solving for column "<<j<<endl;
ll p1=tri[R][i][j-1];
ll p2=getCS(j-1,i-k+1,i+k-1);
ll p3=getDSD(i,j+k-1,i-k+1,j);
ll p4=getDSU(i,j+k-1,i+k-1,j);
ll p5=a[i][j+k-1];
dbg cout<<i<<" "<<j<<" p="<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<endl;
tri[R][i][j]=p1-p2+p3+p4-p5;
}
}
dbg{
for(int i=k-1;i<=n-k;i++){
for(int j=k-1;j<=m-k;j++){
cout<<tri[R][i][j]<<" ";
}
cout<<endl;
}
}
}
int main(int argc,char* argv[]){
qi;
cin>>n>>m>>k;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
//calc for the col sum
for(int i=0;i<m;i++){
colsum[i][0]=a[0][i];
for(int j=1;j<n;j++){
colsum[i][j]=colsum[i][j-1]+a[j][i];
}
}
for(int i=0;i<n;i++){
rowsum[i][0]=a[i][0];
for(int j=1;j<m;j++){
rowsum[i][j]=rowsum[i][j-1]+a[i][j];
}
}
//calc for the dsu
for(int i=0;i<n;i++){
runDsu(i,0);
}
for(int i=1;i<m;i++){
runDsu(n-1,i);
}
dbg{
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
printf("(%d,%d) in dsu %d ind= %d sum_until=%d\t",i,j,dsuid[i][j],dsuind[i][j],dsusum[dsuid[i][j]][dsuind[i][j]]);
}
printf("\n");
}
}
//calc for dsd
for(int i=n-1;i>=0;i--){
runDsd(i,0);
}
for(int i=1;i<m;i++){
runDsd(0,i);
}
dbg{
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
printf("(%d,%d) in dsd %d ind= %d sum_until=%d\t",i,j,dsdid[i][j],dsdind[i][j],dsdsum[dsdid[i][j]][dsdind[i][j]]);
}
printf("\n");
}
}
proceedL();
proceedR();
//calc left up corner answer
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
// cout<<i<<' '<<j<<" "<<a[i][j]<<" "<<max(0,k-abs(i-(k-1))-abs(j-(k-1)))<<endl;
f[k-1][k-1]+=a[i][j]*max(0ll,k-abs(i-(k-1))-abs(j-(k-1)));
}
}
dbg cout<<"ini="<<f[k-1][k-1]<<endl;
//move to the right
for(int i=k-1;i<=n-k;i++){
for(int j=k;j<=m-k;j++){
//move
ll p1=f[i][j-1];
ll p2=tri[R][i][j];
ll p3=tri[L][i][j-1];
dbg cout<<"F "<<i<<" "<<j<<"="<<p1<<"+"<<p2<<"-"<<p3<<endl;
f[i][j]=p1+p2-p3;
}
//move down
if(i==n-k){
continue;
}
ll upt=0,downt=0;
int up=k-1;
for(int j=i;j>=i-k+1;j--){
upt+=getRS(j,k-1-up,k-1+up);
up--;
}
int down=k-1;
for(int j=i+1;j<=i+k;j++){
downt+=getRS(j,k-1-down,k-1+down);
down--;
}
dbg cout<<"F:"<<i+1<<" "<<k-1<<"="<<f[i][k-1]<<" "<<upt<<" "<<downt<<endl;
f[i+1][k-1]=f[i][k-1]-upt+downt;
}
int x=k-1,y=k-1;
for(int i=k-1;i<=n-k;i++){
for(int j=k-1;j<=m-k;j++){
if(f[i][j]>f[x][y]){
x=i;
y=j;
}
}
}
cout<<x+1<<" "<<y+1<<endl;
return 0;
}
Main.cpp: In function ‘int main(int, char**)’: Main.cpp:268:117: warning: format ‘%d’ expects argument of type ‘int’, but argument 6 has type ‘long long int’ [-Wformat=] printf("(%d,%d) in dsu %d ind= %d sum_until=%d\t",i,j,dsuid[i][j],dsuind[i][j],ds<...>