KRectangleIntersection

SRM 778 · 2020-02-13 · by jy_25

SRM 778 · 2020-02-13 · by jy_25 · Brute Force, Geometry, Sorting

Show categories

Class Name: KRectangleIntersection

Return Type: long

Method Name: maxIntersection

Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, int)

Problem Statement

You are given four int[]s, each with the same number of elements: xl, yl, xh, and yh. These describe a collection of rectangles. The sides of each rectangle are parallel to the coordinate axes. For each valid index i, one of the rectangles has its lower left corner at (xl[i], yl[i]) and its upper right corner at (xh[i], yh[i]).

Given an int k, find the largest possible area of the intersection of k of these rectangles.

Constraints

xl, yl, xh, yh will all have the same number of elements.
The number of elements in xl will be between 1 and 200, inclusive.
Each element in xl, yl, xh, yh will be between 1 and 10^9, inclusive.
For each valid i, xl[i] will be smaller than xh[i] and yl[i] will be smaller than yh[i] .
k will be between 1 and the number of rectangles, inclusive.

Examples

{1, 2, 3}
{1, 2, 3}
{10, 9, 8}
{10, 9, 8}
2
Returns: 49

Three rectangles: one with corners at (1,1) and (10,10), one with corners at (2,2) and (9,9), and one with corners at (3,3) and (8,8). The optimal solution is clearly to take the first two rectangles.

{472535635, 143207838, 398752001, 102535995, 309155408, 480522905, 395449443, 331794182, 113194672, 49507477, 397277940, 138748599, 397512329, 41328148, 498876240, 196993133, 233662167, 203385491, 84861337, 321305304, 267828155, 401530676, 195843232, 279205037, 350200721, 237246800, 80970304, 146098455, 346828318, 61718298, 498948344, 372830266, 325788475, 448960428, 413739315, 407631178, 121341221, 237042226, 139898167, 465489501, 50635155, 373896652, 96791958, 121521899, 404338995, 403215683, 307310255, 191401115, 178362166, 190086327, 293732556, 225641521, 448082822, 334434299, 239370548, 231958021, 162108445, 337648455, 53027369, 72931369, 118002411, 274499770, 147842720, 225562148, 296981638, 340741305, 293138071, 228475853, 462386659, 48270520, 434537477, 60289769, 354457562, 372457557, 408910567, 339876115, 180793630, 414936863, 305009901, 217150507, 452386113, 362875678, 217378400, 262307895, 285990366, 352123740, 137785163, 53188718, 42171893, 203824036, 403640164, 80091739, 126987387, 315290468, 185427411, 247182609, 481670731, 17981978, 455516480, 118326450, 450831663, 119959963, 480959752, 107383497, 453946566, 38745783, 228473720, 427160543, 71070965, 302738944, 28145903, 183796107, 476674843, 294382156, 23590585, 106310099, 394731197, 361623543, 297979351, 228477093, 203202975, 456319245, 72114904, 253358368, 355886010, 308688062, 134099260, 87530367, 57457892, 359657245, 166486282, 206647993, 348606996, 434856850, 373096153, 482868201, 15347659, 303456428, 276754223, 88317189, 6376248, 381130480, 95539932, 43191373, 314592521, 194013346, 168860400, 298281296, 240680858, 366596190, 300669805, 210681668, 300524163, 399257449, 452184811, 171359158, 301295711, 111084332, 11719570, 84225979, 75542812, 174316733, 380392921, 385661306, 264352232, 418806122, 235919357, 252371649, 49768512, 453041164, 32704572, 249796148, 61126743, 320466066, 256776654, 304845871, 207839465, 70697586, 394152117, 208848372, 69741392, 50104816, 121622606, 221664872, 283402014, 448046360, 494270191, 211997053, 178252876, 176274158, 69233838, 100230157, 249519446, 2702332, 274676247, 86645272, 294791803, 8506842, 429880170, 245620304}
{477991443, 243627619, 109230682, 120540067, 227428744, 108477690, 316741572, 451491323, 453485043, 220885254, 352733764, 487047673, 117224300, 264761382, 221483950, 242238484, 325195622, 28763709, 378520649, 345703752, 421403375, 154358307, 145020384, 169266140, 391798484, 435797539, 316435969, 72652832, 260855641, 396758697, 475564245, 83151445, 391360627, 374452820, 245807971, 138448318, 55815680, 347343581, 486540974, 343970144, 105300183, 359262402, 57783760, 54600077, 220827786, 163656379, 131879946, 172636016, 373536969, 103327658, 272800707, 112131602, 430991672, 220316833, 438279861, 214884322, 146834705, 224745081, 74038261, 342990462, 389267363, 249251926, 183205530, 137796188, 10211765, 87705690, 64447925, 297130204, 402903447, 296034922, 382560012, 145700173, 389276884, 350840743, 261480191, 136900267, 210551721, 59201858, 167626458, 496301399, 81214812, 466742933, 272692575, 370013286, 404803256, 34089689, 298028228, 182031465, 129848226, 466722058, 118272948, 29952414, 180488154, 336827240, 418933198, 469194971, 342109413, 137003161, 413527734, 373732272, 323119124, 493319977, 72082328, 450729318, 476290812, 266511625, 347630195, 389262427, 321737618, 456690321, 27415601, 254129876, 157640935, 1247598, 322473150, 376692859, 258100001, 480674702, 98612175, 439080233, 262215581, 93598596, 92616325, 23676951, 449966756, 340898542, 176779530, 438538742, 399079842, 200128210, 135408225, 375044887, 498366403, 418472710, 353101388, 482372517, 382864656, 228203715, 150277265, 441326581, 309989258, 119165423, 261197759, 130404575, 161351428, 260592249, 251227871, 119572761, 60146810, 383944892, 336174424, 383635612, 12338699, 359998406, 257233156, 234431187, 496214900, 389988423, 393645827, 87549104, 107241038, 354109537, 182826938, 247023027, 444411891, 259902381, 383210724, 173308135, 244976810, 441096165, 192189850, 154881720, 13297923, 314797738, 231865243, 160561781, 211155875, 231380078, 342957692, 153553526, 92525919, 448304801, 85000606, 58865587, 445825951, 149194671, 17140187, 408822417, 167508656, 150013100, 56120674, 231294388, 366929635, 121471054, 498718853, 366586953, 408750052, 315476951, 319837920, 52920482}
{715281533, 998089127, 897824070, 893221920, 807408265, 967241253, 606014099, 885775069, 850827380, 901175441, 603655675, 921256453, 963673331, 987502872, 545575928, 983156896, 815895529, 962718280, 671734319, 553164163, 872544123, 886950283, 880253305, 859917430, 864384988, 764698898, 951238642, 974248839, 562927000, 639838147, 792183580, 619000273, 712433085, 662741207, 938070525, 880882771, 745232512, 712486679, 906407820, 919317000, 707711557, 944695867, 615994101, 566861452, 528638606, 526332838, 834265076, 680704156, 620705480, 901514096, 748199936, 966011724, 772752316, 939241929, 899322156, 635167374, 568274621, 751962886, 774945808, 999515401, 785698183, 901151750, 544035556, 634057757, 586228626, 829429900, 762139477, 860209708, 652440947, 993602065, 826922905, 846383473, 969138159, 584022827, 633665484, 640067518, 642439632, 816632944, 717830514, 696146186, 758349487, 882145384, 861846455, 536706437, 876162312, 552752032, 560701670, 674834912, 950054039, 833120251, 995675364, 526443020, 538096227, 868375382, 576554741, 547886307, 572190680, 732613607, 550394555, 540681097, 852366157, 820263708, 819318150, 735797864, 956601513, 818744797, 541510630, 916590859, 719712383, 974332740, 701057163, 704923827, 782417933, 572132458, 555494417, 722171224, 712947309, 578212448, 801477581, 795987028, 811955224, 693903566, 801495541, 601350063, 651841055, 880058303, 851210371, 967304375, 706370551, 533830524, 630234965, 885844936, 920997533, 961161379, 519240933, 576232524, 776984562, 707613261, 813794780, 545345683, 756079828, 848967653, 598381145, 563377841, 909456039, 572604605, 500109462, 768722684, 678388830, 528573041, 988608537, 647351695, 753842673, 527677587, 757233802, 659910967, 818691173, 939664485, 840316600, 519496609, 576706105, 918423073, 721074338, 592102811, 693398752, 697040371, 587408099, 653148876, 758144860, 924702983, 994836465, 771031114, 786961949, 889610193, 559961393, 525542444, 884342992, 748455752, 742827049, 788567745, 581485946, 567256765, 625834692, 503738937, 699083268, 545204582, 695715800, 997980074, 831290273, 693539583, 596078236, 961391721, 917999938, 989684305, 905103031, 988016011, 521968142, 545731762, 992246701, 919869754}
{576156674, 836331805, 925421192, 527316926, 890731494, 746885414, 723701804, 874363806, 907469654, 763382696, 770315056, 682100989, 809008302, 518645561, 927647837, 884266949, 735088997, 795122834, 709749415, 805096617, 586753315, 786276773, 873421194, 802028650, 582491923, 556321771, 680646953, 940786099, 641393108, 900655932, 795288523, 740315744, 867795400, 915143873, 589713044, 778598016, 763991631, 511387105, 542001046, 796055030, 708129595, 566047027, 717984741, 828857822, 973516538, 811819717, 821036429, 552005263, 845200557, 730661549, 653359915, 924706698, 537750376, 653129371, 868414089, 981178786, 729416256, 632900046, 741273915, 786607731, 849095348, 958830930, 838315835, 501803587, 799577194, 881541936, 920129724, 565041542, 816743836, 739050110, 656965680, 759526259, 686859289, 693021406, 542133735, 867442478, 623515141, 578938261, 579581891, 861983208, 642484525, 839757275, 593417569, 955046444, 757454419, 973214303, 650069526, 527473615, 504325990, 968700359, 714933848, 653426759, 571885755, 717537382, 713101197, 982536559, 857248831, 980148983, 833569225, 723479991, 739294156, 667237594, 644200910, 804012794, 989805925, 921534813, 939464287, 576930787, 542985601, 701137445, 573086154, 945429218, 843709062, 694218506, 730070674, 704833621, 659215068, 729125565, 906023019, 718319680, 801433585, 893252674, 958601815, 561750882, 810100244, 765434198, 589476200, 843822074, 716874457, 637614137, 986335152, 555047637, 967504387, 976502919, 838539406, 690203459, 988509362, 865904465, 722751789, 783704623, 851662284, 824971301, 619903687, 660782966, 539292077, 878754265, 933471526, 802287729, 503657933, 857644409, 700125794, 924105809, 748427196, 670617785, 879445971, 749269717, 697891899, 720091734, 607327157, 916312285, 852007544, 501250528, 668141357, 793966685, 845616954, 809374484, 766392385, 990520359, 856163145, 812400262, 577092030, 679130380, 630139880, 975593744, 633714287, 607257490, 963649772, 985267746, 839424686, 891471126, 867401767, 948170312, 774723616, 928213432, 584492400, 622326227, 820357954, 851567755, 561878767, 954305785, 864023607, 711640235, 842235422, 693797916, 529888698, 617116334, 875588858, 771352873, 671176376, 530344546}
149
Returns: 9941736382413940

{466751629, 206188687, 62170174, 231920605, 90139982, 355057488, 3640329, 38859891, 207426137, 241611367, 157653990, 400041000, 125998474, 497656877, 460085274, 220646797, 263104212, 336409257, 301266960, 485836900, 58129186, 170579369, 102951016, 325543677, 408963789, 409871082, 232783893, 248802898, 385904661, 378675643, 223935141, 100273883, 186658174, 384779682, 140096562, 421458451, 272502782, 170407525, 422844191, 264484201, 426687030, 355907904, 360995187, 46382372, 255116735, 213492833, 227552264, 469121040, 211364959, 204653304, 280858874, 2435349, 416928112, 187914855, 215180479, 227898425, 166416421, 386060307, 61303340, 423470527, 326098244, 332802018, 51053041, 248302686, 420214762, 99429531, 70208477, 59626213, 192033556, 255436616, 373842364, 80543877, 39152188, 474559497, 273797242, 183886366, 397804248, 85348285, 326581131, 273986162, 441436194, 189933214, 140778504, 312890754, 341158748, 224359715, 161382212, 338560560, 69276170, 124437731, 195859835, 297084486, 284349884, 273886037, 253091985, 498699207, 141768050, 244286769, 30363869, 7685327, 457294738, 381466364, 283123999, 15029304, 49620405, 178131917, 323888722, 134088264, 434328818, 134020808, 346520478, 233702026, 340836128, 225854277, 24086073, 263051122, 166759223, 109885870, 61514830, 128245868, 193327083, 9799240, 406605805, 408458159, 224011132, 220609131, 172407948, 46049189, 245799385, 151908692, 43480402, 139988395, 230866799, 474634635, 286710223, 389342367, 451757731, 389237264, 395156699, 41710552, 336724937, 208221013, 135012067, 278206642, 204043631, 428567678, 321341357, 202492173, 104147592, 361983234, 8750511, 295987187, 461791084, 206254011, 282187543, 271277938, 383552203, 13806363, 146157938, 318832372, 61740946, 148260310, 437502647, 253704866, 497480342, 237139944, 281891440, 478400566, 10474313, 347674348, 243895797, 284380963, 153783569, 310818037, 352546595, 446012587, 144814092, 285354771, 400686199, 413329717, 254435366, 157778924, 258316299, 198782277, 456954029, 88737677, 456363750, 494218786, 404931289, 40020785, 199654702, 429169381, 33940537, 477985704, 499449237, 17688120, 116278658, 315266929, 108429317, 298789910}
{334521997, 205600524, 46716530, 165996846, 326269169, 495176838, 51430528, 320519043, 241071131, 313146607, 367051928, 10832146, 14037642, 440142663, 391966942, 127242598, 285560109, 435890961, 184997408, 102702959, 407412533, 412298105, 61467499, 207198172, 313343506, 82985980, 77003279, 488027769, 428176769, 181202006, 195474864, 40256008, 367642908, 126507994, 159163628, 359092360, 67376769, 44881648, 273953017, 252879647, 400284464, 360530723, 226212444, 127586791, 354244323, 130700315, 438890364, 356466252, 290286877, 235599072, 29668019, 358634870, 43071468, 217948645, 331351568, 277068701, 263029078, 279190685, 490834138, 110455896, 113608295, 51072861, 141074503, 135361690, 336681013, 451390326, 47359770, 194492340, 486328651, 442888922, 450342171, 286144446, 379172876, 55979629, 198200492, 165786289, 95201914, 25041172, 473138961, 329563705, 178611328, 471539687, 410775655, 131515798, 162306121, 430635895, 131614956, 251883931, 116223323, 478891428, 289081204, 3407026, 62280090, 308513388, 32809680, 208764854, 153759053, 66790866, 43699133, 30727047, 195411457, 456173925, 246045380, 221085798, 137619019, 46048851, 386983687, 369735028, 174944191, 44960705, 399685845, 93608584, 82763979, 180192201, 380558401, 453091448, 381102110, 360629321, 436130514, 485298089, 427916595, 22870612, 112681382, 445323797, 173576620, 222509100, 90566585, 213549829, 277255796, 209661188, 487179498, 161854464, 302583139, 483448796, 50856751, 267449789, 220290664, 407986131, 124827978, 295107952, 437039639, 378038029, 81292126, 446453800, 25203683, 447550950, 165967071, 451610657, 494016155, 47161268, 176840528, 38793671, 119072117, 422142806, 368153524, 465951681, 411739568, 12285848, 288587803, 138252816, 80230720, 463234288, 272159325, 219446635, 262886815, 10886529, 105871014, 188598368, 374061426, 422248991, 121634597, 229975914, 119046717, 97668861, 27119297, 58681100, 197400596, 273524789, 378767507, 402317054, 297273755, 410337769, 396526917, 159330221, 378778965, 69729099, 115477691, 5545614, 235125241, 245588165, 47245064, 185292855, 200214356, 20827147, 261476386, 460224257, 26741236, 293513824, 315320532, 418786088}
{500202417, 941067019, 960027121, 959354410, 689075277, 610460435, 515478286, 555474462, 929117960, 867189693, 697203626, 601423704, 812328305, 507670438, 599562641, 924924391, 769354363, 646920451, 931985139, 613231422, 713326110, 888506580, 604415831, 750267605, 558391872, 533594218, 949044755, 868347439, 607817999, 611816839, 553249800, 683619944, 514432805, 560760344, 533662768, 526675998, 545600677, 980802122, 522299746, 827361960, 505442175, 750403808, 798541011, 938916509, 733422039, 734605134, 520074730, 741914670, 530633545, 584100187, 799039350, 506347590, 551469738, 577695982, 904762323, 993065049, 967418998, 879407369, 609523151, 766570780, 993905603, 700809010, 801480529, 919228677, 659473310, 856513483, 678478503, 757252178, 558078107, 833667027, 674121289, 503363383, 575095990, 568998228, 668154229, 896689524, 952541897, 700608529, 818457506, 969567942, 507222750, 901927000, 683566850, 556558367, 675363473, 823168428, 766743463, 562992767, 701920589, 927380472, 688344593, 941818118, 621499701, 760217935, 733433384, 860834550, 950375302, 655602691, 985206657, 600734973, 860678656, 917213611, 896429036, 583515713, 656287548, 731631539, 534665151, 897210788, 989190687, 900074601, 608866149, 540680776, 871497769, 906494355, 960778733, 586108320, 963781208, 779648886, 936410617, 524547732, 870843246, 702628199, 900355016, 760479154, 838067480, 590329908, 923278344, 989145613, 850286756, 937393059, 863862473, 989135085, 556111709, 616811491, 964750284, 983679032, 646565580, 773446402, 923694153, 815373306, 549398527, 738281352, 946239022, 706241850, 598507121, 575691628, 840942307, 643153074, 739753967, 838094291, 731278683, 941553947, 562729065, 507156879, 551424657, 562855332, 640526117, 739094114, 518513049, 539229533, 600003601, 847771429, 973649418, 753310902, 974768369, 659484968, 937216279, 714451816, 651885971, 893966125, 522802889, 723174689, 635025587, 969025305, 837161875, 894342096, 949630036, 636233784, 962540299, 967722426, 702581413, 681638802, 792625960, 616583497, 919845435, 711426856, 888423946, 510623141, 924678010, 868444665, 649945482, 731050123, 523304027, 806162677, 991818172, 999621540, 995745108, 738667745, 752101401, 925708737}
{565662804, 870475021, 918414241, 941858727, 941465702, 800069104, 853588428, 596829633, 859135629, 781771563, 865932572, 613364732, 766901072, 783525228, 803717932, 609904206, 591648653, 930390953, 781377355, 676181927, 562907882, 735849786, 753270497, 700077428, 728282660, 739529023, 554505127, 689077837, 652557299, 760931891, 522288627, 685308223, 780846788, 532745702, 647582120, 501704561, 762746464, 728123317, 923173177, 601398154, 719834859, 688172621, 628316066, 606851892, 732994868, 660840422, 614311596, 810610903, 806019444, 584876397, 957059180, 781439004, 656333038, 601203341, 902666111, 515267209, 713410800, 835932489, 703252781, 867616900, 754463907, 822062016, 690158512, 902165474, 714937961, 587677565, 666743661, 720606254, 666852388, 841535126, 582249052, 796326119, 925307441, 768465848, 537771854, 985622272, 614849261, 937733176, 973456784, 773860373, 779861605, 572779620, 897164552, 626794898, 755985710, 666579717, 675586938, 608987712, 865758213, 845928653, 662978937, 608021619, 735863457, 608017945, 780325232, 503587594, 812470039, 578296296, 718156067, 692658018, 969446504, 911359832, 825256211, 730068509, 516544441, 819105176, 559996292, 901578832, 907444677, 989237135, 924771389, 721571105, 820675243, 954542342, 657009926, 586419900, 612262857, 770613709, 912987616, 589915161, 764533475, 723188496, 853996166, 606058099, 959575346, 937907687, 937150149, 935701445, 881742731, 737171269, 800245551, 788129421, 562613391, 747759948, 921978466, 861533397, 913357479, 694491085, 831453665, 958193230, 648065116, 901167665, 646422340, 938926248, 961431149, 811373530, 632905483, 807370286, 700517174, 602528767, 568408137, 964742471, 697092667, 872535902, 748310260, 950668209, 969342970, 910943262, 858850397, 722159425, 738747151, 673110938, 840038970, 878514127, 971178276, 631346110, 805748846, 559933325, 501280999, 894420851, 926568808, 727060965, 994886969, 665578535, 910972959, 565801322, 827379913, 876325100, 882647753, 725577994, 815372121, 807181263, 566526201, 943296172, 562110711, 903143454, 522382291, 739009884, 956217355, 675002923, 990351527, 964893160, 949949719, 793286398, 909785839, 866293499, 676472125, 639120109, 757590909, 600809446}
20
Returns: 287923919236404640

{443620804, 186189471, 262865362, 124576514, 142171427, 96763365, 382017322, 254611999, 15696872, 398502932, 10876402, 439379407, 287944037, 8436949, 42283003, 497386563, 329724026, 49066309, 475816803, 115102349, 461916433, 194793449, 105019526, 237404211, 381623584, 82579178, 155250004, 371092967, 496054795, 391764176, 311725078, 163904862, 362048119, 429607633, 289824114, 368967147, 241829970, 182935898, 61781426, 264746047, 421901855, 267573753, 97116463, 411926055, 221167246, 158315758, 283010776, 9628760, 401456248, 417137999, 218642141, 395917097, 324285207, 379965892, 290436182, 59339565, 81022074, 364002068, 301817657, 153770325, 467126591, 294945061, 224073595, 204524635, 231626292, 346575067, 389483806, 364187758, 467315785, 365057827, 2843878, 41407430, 437489874, 96802667, 415633139, 358915981, 443142221, 1322624, 131364123, 308715699, 200025923, 264485118, 161495451, 61247983, 482673429, 276546153, 268112575, 173610368, 324465131, 231227934, 439913357, 350829076, 414024117, 302469186, 181322743, 281775912, 58940380, 293545813, 416944107, 368243195, 610042, 399527952, 197136125, 196508122, 441230505, 417073867, 383604953, 18917525, 2828293, 492439884, 103515518, 495179329, 91607773, 209600142, 53148616, 1068318, 73684375, 209822425, 9355140, 322280293, 438194115, 301861930, 106012297, 10420823, 156144765, 291820589, 6151143, 81963564, 205955848, 113865648, 172249705, 199523228, 346477487, 251295432, 74370638, 172208278, 367769881, 270620592, 49747863, 496270257, 404413499, 79626677, 276594959, 291752989, 193946547, 116729953, 151681304, 196745532, 149637123, 378865831, 323621485, 127556117, 407265178, 423235523, 334488050, 242188586, 211212057, 242918662, 188868198, 178186433, 84433727, 62719966, 396614674, 242145789, 163934006, 148527067, 415701223, 2482798, 180269832, 311830646, 2412723, 91342344, 297925865, 162467002, 99739056, 48677687, 99274541, 290125886, 247264715, 219761852, 37335608, 235356738, 293423280, 10768891, 374068789, 146869089, 450648128, 29079342, 20780922, 113514784, 364398043, 426079686, 311754732, 332854515, 155586572, 154352682, 371018722, 84147782, 130169166, 390082446}
{409639394, 30386835, 99791750, 346993531, 8717219, 187114293, 171034895, 474480067, 252957208, 193090781, 93515650, 200213905, 308518938, 6934603, 481305772, 169839811, 193543430, 306360141, 396722302, 195966434, 280991145, 324252572, 463549381, 360376261, 45661360, 255914248, 223439974, 211468471, 188141526, 126756434, 277793656, 229182756, 292745301, 338501499, 201485747, 51618017, 394290432, 22560812, 258067658, 440551215, 200687218, 181033506, 440229676, 419818228, 287430005, 158349474, 469692161, 379836365, 261825799, 349746011, 159563948, 434418939, 32642377, 306204069, 247941593, 355747291, 469715131, 146818036, 431914138, 21931928, 79503646, 416943082, 437630598, 74259132, 188997693, 47580656, 254232782, 489125874, 304775841, 256766286, 263229832, 412456508, 180049656, 370476448, 329120736, 425346063, 305807241, 279091987, 391534957, 13784625, 146451314, 155033730, 294023605, 269416351, 76856498, 302349835, 370602889, 420115798, 228229257, 342955566, 427581021, 142179219, 91560197, 318322632, 215582366, 403033808, 473512267, 81512580, 435741643, 52091556, 420020235, 50779047, 139954131, 19528806, 468941258, 44185404, 328063941, 483744340, 42686819, 446093246, 334771554, 153606942, 77982918, 478116592, 62867331, 179636238, 252812291, 64410561, 27290969, 193082661, 140494163, 367188572, 236650347, 117697229, 202795837, 401829297, 295938183, 299905338, 408175413, 434483730, 358592554, 381066464, 162206507, 1587432, 119795253, 143953, 293339444, 116098006, 52581237, 149178002, 90498172, 400740070, 474954972, 447215316, 335086872, 214958329, 239582552, 233191626, 28552724, 316382337, 460070066, 461505390, 11052291, 253890074, 481129940, 279212701, 366267145, 333657150, 204475376, 445740654, 321469660, 40438040, 56288122, 122764166, 374744873, 156040034, 62697993, 29351203, 482093449, 102868531, 24154689, 466400155, 178747591, 51548434, 421153871, 474493512, 218896569, 450622800, 123299959, 26464886, 499905617, 287238977, 231783899, 325279738, 410365641, 248583143, 469019626, 75540856, 366903952, 233747077, 372793195, 241587280, 197183182, 375135100, 258826409, 362002970, 34213810, 330578502, 348008028, 90143355}
{989273589, 771476749, 817557935, 927316794, 516394216, 967133820, 816140494, 672926786, 708329069, 897554898, 533492022, 928546099, 779657994, 742570811, 817644243, 921530863, 531041059, 671873921, 913568920, 711407741, 908736625, 842188083, 828194199, 946760527, 846200662, 876904047, 532443541, 666846877, 894024774, 648164192, 631317708, 955224528, 730534408, 882176439, 943698358, 594733993, 927904738, 795683653, 635806375, 570149626, 751695246, 774747184, 732854516, 899035572, 833917442, 913770556, 731320143, 649070216, 580730610, 821323839, 934058842, 608874847, 637110903, 528423642, 620924584, 987055879, 858648649, 602109771, 889055437, 524884125, 982109544, 571217692, 681335833, 730969495, 875120324, 908267810, 715261460, 536253445, 944800612, 617646350, 930800041, 573077705, 655674599, 693483870, 611193084, 721736213, 771031715, 817142911, 550661853, 964882408, 710457650, 822161374, 902000624, 931318781, 738289109, 933591839, 668527032, 683800253, 747700798, 830420953, 649884666, 965949079, 859783492, 754765912, 941574671, 513624366, 587179816, 584083374, 850558885, 952362011, 507833751, 891039113, 549978216, 799627398, 573093986, 799295592, 975930594, 695097807, 529073983, 695082563, 719987569, 948782784, 588976665, 627539786, 988349342, 690377406, 882069935, 775093770, 720136069, 981784859, 702832932, 605394395, 514990470, 614443360, 804457551, 983324258, 510871634, 910589025, 863221341, 501114092, 738549823, 848676811, 654903183, 863953472, 966271130, 543666570, 732015099, 815609298, 932779654, 559734918, 991762480, 814352665, 749724606, 905953654, 894327191, 549911793, 621385017, 653555276, 848511617, 765002647, 646647679, 623822451, 955369218, 822558831, 581475598, 563130921, 710806447, 689388308, 542118810, 621710187, 707623748, 578674937, 945768393, 723157529, 636731041, 647159673, 752225880, 610395833, 785752203, 993351597, 838793315, 704472283, 530131305, 505037353, 671868431, 665565172, 894678657, 871720987, 867760748, 944908530, 519672136, 648468594, 836212847, 980789015, 848324552, 524051147, 845544920, 759106181, 584144703, 982883159, 746246574, 754515651, 538641170, 807758659, 763138705, 543885680, 642241677, 553542809, 557444924, 846225323}
{728827638, 758604316, 960658150, 576852635, 616430884, 754725466, 505332457, 799496582, 579540016, 678375013, 950379055, 814857937, 809666572, 621811216, 720796666, 604195510, 992165387, 531729433, 856111505, 629247494, 719717082, 516876090, 964600069, 700479771, 676816017, 534366646, 770425633, 558659740, 799519163, 590386521, 879365135, 900327099, 621026129, 600714269, 602651041, 712002433, 739793876, 772429308, 770216906, 671806935, 965610929, 989569391, 902509046, 763561469, 998216234, 837760131, 915497299, 583774566, 551563364, 547913823, 974031425, 769858371, 645436919, 725571840, 958507381, 654310131, 765615176, 782905139, 812489168, 524484088, 669285198, 872791689, 622895648, 596018743, 512870218, 766906954, 561266323, 697191654, 687842664, 769328523, 765235093, 974571071, 661817877, 934681276, 692848813, 954675876, 507110167, 862465851, 855018310, 612307475, 867811424, 578082505, 575202233, 585740294, 808082200, 873008728, 791381673, 621406470, 891569329, 648707705, 709362070, 706995831, 611384059, 909924596, 909725896, 548160861, 600544185, 792716349, 898931186, 760873893, 750592485, 570938769, 787673557, 654747935, 870557368, 931829183, 567903263, 698330162, 793810583, 556983162, 945255193, 772345417, 937944457, 518143889, 903966280, 942734051, 979605269, 854259554, 542232489, 762175035, 635538999, 745424633, 823664064, 740861894, 837709387, 777996838, 587745494, 638557415, 777934129, 890443831, 994809265, 588711608, 829144471, 677916758, 704118968, 789450600, 579369622, 503608111, 949609667, 642496982, 830610418, 822331432, 710410758, 693488812, 774502621, 569497684, 791141692, 839377413, 620234468, 550483549, 572658431, 708437522, 809415866, 660450704, 985813708, 524374082, 902458051, 666983860, 639567599, 618785593, 585547304, 810129471, 541681148, 766649619, 876569377, 560255948, 989841092, 855482950, 713572657, 550917556, 812678290, 507954139, 730772933, 955375824, 811666853, 816501227, 648283206, 994696197, 828079106, 789560161, 710859037, 833857086, 836252277, 566693186, 571971954, 642643148, 939794314, 585387062, 873435414, 594438310, 781560728, 804923259, 635991123, 908281434, 687287674, 605797991, 911632894, 872076024, 563992461, 931613898}
47
Returns: 100001925791439875

{320920798, 495463952, 35098726, 290600698, 22375248, 473542070, 474700709, 54296808, 250088737, 109634644, 204790310, 300059055, 136196784, 137753298, 302451715, 472174608, 245122561, 169001163, 116994771, 85719660, 170223197, 292076894, 236001306, 323159480, 55255483, 328904394, 413380953, 308754536, 47825325, 486250202, 210841427, 41287200, 62374926, 1207991, 159905585, 112481099, 341477313, 225748085, 423276157, 253863340, 101207039, 444613742, 349387731, 302382302, 22098797, 403186293, 482807683, 253962358, 48938700, 134743136, 423123248, 486026529, 34305950, 338417335, 270876809, 404925892, 134774758, 252395614, 122989077, 161059009, 146374542, 281842865, 43770100, 199446582, 472603788, 442732384, 198284066, 88922659, 181711460, 183045117, 382627608, 354454571, 382188203, 132226228, 70039657, 127563201, 381553782, 113640608, 351754583, 86746491, 1693757, 147115769, 44991841, 214332466, 2702679, 64191485, 321843905, 85819641, 47198306, 53491511, 117043046, 321707132, 90039805, 93107030, 431357599, 473079198, 1330936, 100774697, 86071605, 193810065, 452755904, 169348891, 278993941, 175921406, 368702796, 367608305, 173640235, 382734718, 453764630, 319126825, 69781226, 50872839, 20105915, 54208258, 39769747, 346501552, 203254871, 373047754, 293143521, 455392996, 284293906, 395426072, 78416018, 127429683, 397497709, 161520692, 55456761, 361938204, 207549472, 51332132, 86077087, 237313393, 4838932, 464077113, 50345611, 274616116, 354747395, 107473987, 421904170, 168177004, 328805170, 195757572, 203040781, 381494432, 353355893, 250514637, 56188405, 341154043, 261780595, 358837876, 236686792, 124694650, 439290870, 311296986, 426797998, 142864392, 24472644, 262793818, 163842613, 289050935, 357477820, 499101794, 3564922, 61881511, 247206060, 407124001, 336559540, 119932587, 371607742, 366170087, 158860514, 442421545, 171797555, 416033240, 310735914, 384344475, 247051350, 123758020, 65709061, 480774141, 31331411, 403077960, 373760118, 238994490, 303270743, 394041435, 147437043, 374213936, 303462319, 405190914, 249343491, 308920539, 441533782, 173211494, 293264427, 108736309, 228299303, 282384308, 261134785, 230058526}
{351371751, 17367133, 1282493, 85075455, 296663804, 493385240, 156206835, 356808490, 358004256, 435529848, 401432224, 178300157, 220634686, 340655906, 121585429, 289794577, 253231515, 300031342, 348794647, 239136488, 412023930, 481498207, 323282674, 89208353, 89586160, 122668583, 38976374, 158524849, 431857206, 374248771, 297071780, 4226499, 113868469, 144703512, 128291709, 92687815, 253896443, 3307483, 406579119, 319904273, 433310856, 30965500, 479440679, 462578177, 139306692, 254745849, 330043228, 156757790, 37508819, 304658001, 189875752, 473135957, 397009828, 346695739, 55772474, 71351182, 397236736, 53939299, 209533685, 416973715, 473152729, 175769515, 339478045, 456811130, 315182777, 245055044, 368552444, 317269045, 457915761, 239739966, 124644865, 343383671, 302537682, 425501668, 90557691, 206590718, 152412994, 438136866, 415552600, 122162236, 66678572, 364613240, 7226083, 319251005, 199020148, 101605841, 351541220, 354505222, 8524267, 62942526, 334155086, 346467007, 179757903, 81436998, 189241704, 152140343, 325812322, 13742841, 141331801, 384145442, 63933598, 287396747, 243180427, 370907902, 73080482, 280696199, 430883770, 314612107, 245270688, 386503681, 425293070, 270183401, 386468695, 156024205, 311012724, 388219795, 57754459, 279450137, 191898143, 222439233, 14421649, 187164203, 179040406, 9644169, 286674786, 290320795, 171165034, 70086636, 358595977, 85604978, 156071797, 341164167, 399866432, 186837751, 4598301, 69000461, 362255066, 483433391, 142675874, 27811288, 88350916, 257228936, 200548701, 445218531, 384533548, 192496783, 17319100, 87143765, 491978170, 159109122, 226565805, 193171364, 478485302, 12782013, 278075287, 122362195, 357144980, 363642866, 79079350, 49745243, 92065034, 317963843, 166518919, 73558203, 436255378, 160091244, 171920030, 79557077, 486504285, 368575674, 230079856, 278718594, 297578143, 453732723, 153478773, 78771095, 198641749, 425444410, 300312113, 305511531, 23967839, 113802926, 61211692, 460676449, 46854923, 377318643, 93748179, 460060475, 437990841, 156069034, 90058218, 448084967, 216354019, 472758444, 152391131, 80076776, 118552294, 240654762, 349147560, 28843179}
{926360800, 547756305, 814306731, 575691357, 823083905, 535020696, 594112311, 838766718, 554323421, 834729745, 809852391, 859833547, 506697709, 976533507, 800765381, 680614588, 665418261, 779187375, 567271639, 889798338, 989908116, 817762563, 960060828, 755504002, 808712686, 684644736, 981498119, 728781569, 750071076, 546818238, 596535624, 617692257, 500273358, 527022708, 511920431, 790581071, 782030599, 729111071, 827831203, 915053463, 877689472, 792111251, 575503628, 949237772, 909007298, 873056921, 753306440, 571213131, 766346935, 548043733, 534842247, 939296900, 775576368, 867041772, 774644408, 972007129, 904904449, 558085065, 508298090, 722217177, 627283915, 542323739, 974084554, 770272090, 628891881, 985106689, 546779001, 772849951, 663948406, 829310247, 598409185, 510392738, 524791993, 827091158, 966870684, 772954703, 785272216, 578296699, 906382420, 668284560, 734384198, 618082526, 782446914, 926559819, 555683920, 520650101, 922043867, 750547478, 935247722, 865021085, 544658893, 840100372, 670921180, 604774893, 522589391, 786654077, 712621103, 816234835, 980509547, 987018908, 868569527, 672202790, 587086351, 500382772, 769455670, 621863222, 745245937, 827085719, 862481827, 721765559, 764446897, 576749493, 980116725, 672929277, 585243324, 989038665, 530179770, 862754125, 947152243, 514931606, 894262662, 838907378, 608210996, 512454354, 695651177, 675571607, 913215743, 720022046, 598200990, 625140954, 725079141, 766695290, 738735952, 705750831, 675602093, 561929489, 820448579, 870753011, 772993083, 956472556, 693668023, 657463551, 961832433, 738656605, 923299601, 704912737, 578633043, 893351386, 582720521, 871912693, 714414337, 700798977, 988808274, 576232995, 872500698, 735809430, 891747785, 555592091, 947635194, 501021536, 628295505, 526926702, 807026794, 929252522, 652358335, 867322851, 525588318, 837771193, 549940642, 776269593, 934776889, 577506904, 802944698, 913052328, 515642101, 705111762, 639892465, 631905935, 681186771, 979649230, 981302887, 934428586, 774693508, 862433275, 530064455, 880138801, 811521997, 919850298, 652507359, 752782949, 941831882, 718718539, 918438646, 767922248, 991035989, 517917978, 693079109, 720627054, 927356232, 795448327}
{727125718, 642099771, 865693149, 974694401, 528867676, 647320870, 769175766, 940588872, 620411033, 785798579, 924683706, 552288138, 604861289, 530272558, 932025016, 726664938, 769150535, 673495211, 730120473, 653332304, 538067751, 839436783, 564118779, 757103773, 509498962, 703540759, 933430645, 752700184, 932168350, 912472702, 611398148, 504840637, 897853290, 545570726, 511294548, 758195225, 880355296, 690767475, 655600567, 616075715, 941139889, 786070871, 508025797, 724574758, 967805333, 830636921, 847320465, 823502878, 570498557, 877180793, 985148421, 740544451, 799298392, 689900492, 700061553, 774553508, 695760546, 767145798, 582404106, 858168450, 752032950, 702530976, 833828778, 953161501, 546407716, 656043619, 685485863, 916046093, 804684232, 760114470, 629788354, 640988263, 788788623, 692749320, 952070170, 988328874, 715972816, 888064224, 771909934, 951558243, 765186314, 661274801, 722418792, 707069444, 882010114, 674354791, 726956911, 970536874, 801556535, 514000567, 911689207, 873277931, 590873348, 921141234, 801803698, 654434921, 766071498, 868534868, 535488273, 660075809, 929746238, 840817061, 749422012, 725720171, 753804007, 729058788, 864449699, 574334642, 561423241, 670249315, 828784850, 712806760, 598011110, 901413337, 603209321, 801965246, 685131698, 604142538, 943862524, 915946818, 862480366, 997168329, 910272125, 659297205, 712742224, 829055835, 528523248, 711513125, 701375080, 626855250, 978310401, 594642949, 786950189, 806847896, 668325049, 694987077, 620921566, 850234443, 813971023, 549929881, 900613987, 705582577, 897411989, 968710291, 865945435, 625291324, 950014964, 869326939, 535975665, 955433671, 589016493, 776747039, 575865313, 706557858, 601540965, 695963376, 726955936, 632281919, 819233990, 520039488, 729378719, 670769077, 977238837, 976823371, 680657761, 942023688, 749871558, 968441214, 865002246, 518177126, 777858719, 746114919, 982206924, 905321204, 507548540, 808630359, 967152002, 921598318, 715929008, 594334049, 629410919, 893810313, 902181055, 778178949, 883016242, 927068712, 965979451, 599951954, 700037826, 797887789, 531899982, 958552540, 635193828, 740974503, 898362880, 577507177, 810580140, 767907439, 931012067, 520282349}
136
Returns: 15967958020359684

101)

{2, 5, 1}
{3, 7, 1}
{7, 10, 6}
{9, 10, 5}
2
Returns: 8

The optimal solution is to choose rectangles 0 and 2 (using 0-based indices). The intersection area would be a rectangle with bottom left corner at (2, 3) and top right corner at (6, 5) having an area of (6-2) * (5-3) = 4 * 2 = 8.

102)

{2, 5, 1}
{3, 7, 1}
{7, 10, 6}
{9, 10, 5}
1
Returns: 30

The intersection of one rectangle is the rectangle itself. The biggest of these rectangles is rectangle 0. Its area is 5 * 6 = 30.

103)

{2, 5, 1}
{3, 7, 1}
{7, 10, 6}
{9, 10, 5}
3
Returns: 0

The only subset of size 3 is the whole set which has an empty intersection. The area of an empty intersection is 0.

Submissions are judged against all 126 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class KRectangleIntersection with a public method long long maxIntersection(vector<int> xl, vector<int> yl, vector<int> xh, vector<int> yh, int k) · 126 test cases · 2 s / 256 MB per case