QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189883#1809. Find the MST for GridKKT89AC ✓38ms7488kbC++17969b2023-09-28 01:16:432023-09-28 01:16:44

Judging History

你现在查看的是最新测评结果

  • [2023-09-28 01:16:44]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:7488kb
  • [2023-09-28 01:16:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	ll h,w; cin >> h >> w;
	vector<ll> a(h-1),b(w),c(h),d(w-1);
	ll res=0;
	for(int i=0;i<h-1;i++){
		cin >> a[i];
		res+=a[i];
	}
	for(int i=0;i<w;i++){
		cin >> b[i];
	}
	res+=(h-1)*b[0];
	for(int i=0;i<h;i++){
		cin >> c[i];
	}
	for(int i=0;i<w-1;i++){
		cin >> d[i];
		res+=c[0]+d[i];
	}
	vector<ll> v;
	for(int i=0;i<w-1;i++){
		v.push_back(b[i+1]-d[i]);
	}
	sort(v.begin(), v.end());
	for(int i=0;i<h-1;i++){
		ll aa=a[i],cc=c[i+1];
		ll p=lower_bound(v.begin(), v.end(),cc-aa)-v.begin();
		res+=p*aa;
		res+=(w-1-p)*cc;
	}
	v.clear();
	for(int i=0;i<h-1;i++){
		v.push_back(a[i]-c[i+1]);
	}
	sort(v.begin(), v.end());
	for(int i=0;i<w-1;i++){
		ll bb=b[i+1],dd=d[i];
		ll p=lower_bound(v.begin(), v.end(),dd-bb)-v.begin();
		res+=p*bb;
		res+=(h-1-p)*dd;
	}
	cout << res << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

input:

2 3
1
1 3 6
1 4
1 2

output:

17

result:

ok answer is '17'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

4 3
1 13 15
3 6 11
3 6 6 11
9 17

output:

173

result:

ok answer is '173'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

2 3
968418
431416 672770 680574
552160 624114
892963 920468

output:

7379244

result:

ok answer is '7379244'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

3 2
118689 499942
45109 920606
327638 468788 633079
149844

output:

2587886

result:

ok answer is '2587886'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

3 3
171815 356177
228641 395286 978617
702666 792511 913883
169671 180825

output:

6127710

result:

ok answer is '6127710'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

3 4
7184 620183
79780 130738 487556 848611
232818 371375 944380
216990 936022 983989

output:

8438293

result:

ok answer is '8438293'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

4 3
51985 136713 427919
188504 312899 371141
145631 227550 731171 833357
160747 573726

output:

5493218

result:

ok answer is '5493218'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

7 5
175926 428984 582661 582839 820907 920776
322080 633264 798688 811692 823441
54339 220390 250291 330054 371881 842806 885846
441838 703407 941999 978043

output:

37806417

result:

ok answer is '37806417'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

9 8
128346 182079 277192 434166 657634 823595 853129 940474
707 292710 363361 404369 494504 600358 796392 872568
95548 456201 544335 582372 695261 827770 860026 928632 994917
160921 262851 319385 402844 959489 982420 982699

output:

69150796

result:

ok answer is '69150796'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

7 7
390088 456793 662796 811369 863901 997123
174627 272343 294065 376553 692154 797046 972456
76702 401950 405513 470226 553463 682122 826908
106803 293625 306370 544706 575270 828264

output:

44304980

result:

ok answer is '44304980'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

7 7
270291 358878 423424 570235 772251 986431
45308 139839 229024 246723 264432 343181 778141
74325 203070 240656 330399 549696 621374 856760
57300 464802 541216 680595 915767 928652

output:

38909585

result:

ok answer is '38909585'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

9 8
255312 314659 435326 436128 464484 507292 727368 807464
103501 293849 414270 474996 838635 874511 965537 971583
204709 230699 251434 494013 570649 664454 741866 906547 910970
419608 622510 678766 703125 809137 903338 923781

output:

76479411

result:

ok answer is '76479411'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

90 15
1569 7812 15560 17225 19225 21440 63872 67763 73422 92647 98398 106522 110109 112693 114487 122224 154052 155699 158235 174012 175798 176730 177959 187239 190924 206750 217783 229076 247986 249130 260497 265264 269052 285315 291931 327499 331976 337424 338165 352012 363333 370568 370943 373038...

output:

1149258768

result:

ok answer is '1149258768'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

573 762
3338 5419 5645 6157 7116 8262 8393 8399 8717 13114 13179 15879 16350 18675 18777 20835 21329 23456 25635 25875 26218 27153 27503 27953 28438 30788 32050 35179 35273 35416 44186 47640 48200 49720 51545 51756 52851 52886 53427 56462 56541 57087 58701 61500 63233 63449 63650 64330 71582 72299 7...

output:

425651347739

result:

ok answer is '425651347739'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

5523 5571
187 355 377 524 572 593 624 947 957 973 1147 1287 1861 1911 2165 2436 2560 2806 2875 2924 3028 3035 3090 3210 4339 4372 4520 4531 4580 5137 5395 5686 5710 5802 5994 6494 6816 6919 7012 7349 7609 7783 7833 7943 8016 8242 8327 8422 8475 8489 8608 8619 8659 8686 8709 8738 9353 9423 9651 9692 ...

output:

30844827296192

result:

ok answer is '30844827296192'

Test #16:

score: 0
Accepted
time: 12ms
memory: 4756kb

input:

13831 51499
63 97 191 216 351 488 604 626 804 844 870 917 931 1019 1166 1183 1376 1498 1544 1564 1624 1786 1930 2023 2086 2197 2203 2251 2288 2312 2445 2657 2698 2857 2932 2944 2972 2986 3060 3114 3119 3231 3231 3380 3385 3503 3537 3747 3782 3796 3818 3868 3882 4012 4129 4175 4387 4652 4671 4744 481...

output:

711055248264935

result:

ok answer is '711055248264935'

Test #17:

score: 0
Accepted
time: 32ms
memory: 6996kb

input:

79795 87752
9 16 21 22 54 55 57 78 80 84 87 119 141 155 155 160 163 173 178 182 184 202 261 269 307 324 343 344 353 354 360 365 386 416 423 441 456 478 484 501 523 558 568 578 583 588 593 596 607 613 614 617 627 658 661 678 680 703 717 723 737 745 755 755 764 794 799 816 816 823 849 913 919 953 981 ...

output:

7001306325946025

result:

ok answer is '7001306325946025'

Test #18:

score: 0
Accepted
time: 16ms
memory: 7284kb

input:

96489 93475
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

99289159465

result:

ok answer is '99289159465'

Test #19:

score: 0
Accepted
time: 19ms
memory: 7112kb

input:

93347 96219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

906400572842

result:

ok answer is '906400572842'

Test #20:

score: 0
Accepted
time: 15ms
memory: 7208kb

input:

93920 97246
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

9132580812335

result:

ok answer is '9132580812335'

Test #21:

score: 0
Accepted
time: 29ms
memory: 7124kb

input:

96820 90892
100000 100000 100001 100003 100005 100005 100005 100006 100007 100009 100012 100013 100013 100016 100017 100017 100020 100020 100023 100023 100023 100024 100027 100027 100028 100028 100029 100030 100030 100030 100030 100030 100032 100034 100035 100035 100036 100036 100036 100038 100039 1...

output:

2640105428447812

result:

ok answer is '2640105428447812'

Test #22:

score: 0
Accepted
time: 32ms
memory: 7404kb

input:

98593 99147
3 9 10 11 12 13 25 31 37 37 38 41 43 44 76 87 103 103 111 113 114 132 135 147 150 150 150 150 158 158 190 197 197 198 223 256 258 282 290 292 293 296 316 318 327 342 346 356 369 377 380 386 394 408 421 456 462 476 479 505 506 513 516 520 521 535 545 553 557 589 589 590 623 627 637 640 64...

output:

9792673258080914

result:

ok answer is '9792673258080914'

Test #23:

score: 0
Accepted
time: 31ms
memory: 7148kb

input:

91723 98082
1 6 8 21 23 26 37 38 48 76 87 109 125 125 137 140 145 181 209 218 222 234 254 260 261 284 312 325 337 341 343 348 352 380 380 395 397 410 412 414 422 444 445 454 468 478 489 496 499 526 535 539 539 551 552 566 569 577 600 605 609 616 618 620 636 647 650 651 661 663 682 689 690 693 700 70...

output:

8969528194993736

result:

ok answer is '8969528194993736'

Test #24:

score: 0
Accepted
time: 34ms
memory: 7404kb

input:

99357 94710
9 53 60 98 129 149 157 167 197 209 232 241 241 244 263 293 297 299 303 326 327 337 341 355 370 375 378 382 390 401 405 406 409 413 444 447 453 458 460 465 471 479 491 512 513 520 526 572 574 577 588 596 597 604 615 631 631 640 660 703 715 724 724 759 764 782 784 812 815 826 828 833 875 8...

output:

9392674678880652

result:

ok answer is '9392674678880652'

Test #25:

score: 0
Accepted
time: 13ms
memory: 5724kb

input:

2 95804
959149
12 12 32 42 47 82 94 116 121 125 131 133 146 148 165 173 182 220 231 244 250 254 256 271 273 277 281 284 286 290 307 322 352 359 370 374 387 402 406 417 418 426 429 429 430 434 440 449 453 469 471 486 486 501 506 517 526 535 543 550 557 577 587 598 599 605 615 615 622 626 641 649 666 ...

output:

155767264270

result:

ok answer is '155767264270'

Test #26:

score: 0
Accepted
time: 9ms
memory: 5740kb

input:

5 90944
124461 465935 619609 995424
6 12 22 28 29 31 43 110 115 118 127 141 150 167 180 180 184 189 191 200 223 238 247 255 266 278 293 298 304 306 307 336 337 338 360 361 366 370 373 441 443 443 444 477 496 516 520 536 554 555 563 567 603 607 616 622 624 647 651 659 673 678 681 682 703 720 721 722 ...

output:

405236079588

result:

ok answer is '405236079588'

Test #27:

score: 0
Accepted
time: 13ms
memory: 5764kb

input:

90142 2
17 60 71 71 80 116 125 132 161 161 184 186 189 192 195 198 222 228 240 241 243 244 258 259 266 266 268 268 294 294 312 334 338 338 383 394 407 421 431 442 454 456 472 505 526 545 558 559 573 584 585 597 628 631 641 644 667 694 697 731 736 742 756 799 817 817 817 834 837 846 880 898 899 926 9...

output:

162938011165

result:

ok answer is '162938011165'

Test #28:

score: 0
Accepted
time: 13ms
memory: 5684kb

input:

96480 4
5 12 28 34 34 35 48 52 61 66 119 127 139 141 154 161 161 177 179 179 188 200 209 211 252 253 269 279 284 302 305 311 311 311 314 335 357 364 368 377 393 395 411 422 432 433 500 504 508 508 514 520 527 534 539 546 546 549 556 564 568 601 625 626 631 632 642 643 647 671 688 697 702 707 708 717...

output:

415048353468

result:

ok answer is '415048353468'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2 2
168295
459668 574522
245590 334049
513757

output:

2130127

result:

ok answer is '2130127'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

2 2
1
1 1
1 1
1

output:

6

result:

ok answer is '6'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

2 2
1000000
1000000 1000000
1000000 1000000
1000000

output:

6000000

result:

ok answer is '6000000'

Test #32:

score: 0
Accepted
time: 17ms
memory: 7312kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

19999999998

result:

ok answer is '19999999998'

Test #33:

score: 0
Accepted
time: 18ms
memory: 7276kb

input:

100000 100000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 100000...

output:

19999999998000000

result:

ok answer is '19999999998000000'

Test #34:

score: 0
Accepted
time: 33ms
memory: 7356kb

input:

100000 100000
1 10 12 19 37 69 86 128 136 147 156 163 168 170 183 195 195 212 216 223 227 239 259 269 272 277 297 314 322 324 327 332 346 351 367 369 370 384 397 432 433 467 484 491 505 525 529 531 535 545 546 557 574 581 582 587 590 603 613 616 619 625 647 656 662 678 689 717 739 741 746 755 793 79...

output:

9992237854779891

result:

ok answer is '9992237854779891'

Test #35:

score: 0
Accepted
time: 38ms
memory: 7256kb

input:

100000 100000
11 33 38 47 49 71 73 78 80 93 95 112 123 125 139 153 173 176 223 224 228 234 239 253 258 263 275 278 305 308 312 326 326 332 337 349 350 354 363 384 390 400 400 409 426 430 435 456 472 476 487 494 498 502 507 511 513 526 558 559 586 604 610 614 617 621 634 646 647 652 660 660 661 672 6...

output:

10001379353918782

result:

ok answer is '10001379353918782'

Test #36:

score: 0
Accepted
time: 38ms
memory: 7284kb

input:

100000 100000
26 26 46 48 60 71 73 83 85 86 97 100 107 135 138 138 138 143 147 154 175 179 190 193 203 217 232 239 243 247 257 258 263 264 272 279 280 295 299 302 305 324 326 327 336 356 356 375 398 400 404 411 425 472 482 508 511 516 524 525 531 573 576 590 592 608 610 614 622 626 628 631 633 634 6...

output:

9993903679912019

result:

ok answer is '9993903679912019'

Test #37:

score: 0
Accepted
time: 38ms
memory: 7488kb

input:

100000 100000
5 48 50 91 95 97 112 117 119 120 133 139 141 147 155 160 187 203 209 213 215 218 241 261 261 262 267 269 275 283 304 326 326 334 340 341 364 368 399 413 416 423 433 438 454 466 477 482 482 496 519 521 530 548 557 561 569 593 600 629 629 659 661 664 680 689 691 695 700 700 701 708 725 7...

output:

9994484733316683

result:

ok answer is '9994484733316683'

Test #38:

score: 0
Accepted
time: 32ms
memory: 7484kb

input:

100000 100000
5 11 20 21 52 59 71 76 90 95 104 104 125 126 130 132 133 138 146 154 158 170 178 185 186 187 203 210 230 233 241 249 270 275 282 307 334 339 382 391 401 409 412 424 425 440 441 446 459 482 532 544 551 553 559 559 560 563 571 578 579 580 586 594 601 607 619 620 636 645 648 655 658 661 6...

output:

9990754292831930

result:

ok answer is '9990754292831930'