QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18230#1243. TerritoriesWu_Ren#AC ✓116ms67284kbC++111.0kb2022-01-16 21:17:142022-05-04 17:23:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 17:23:32]
  • 评测
  • 测评结果:AC
  • 用时:116ms
  • 内存:67284kb
  • [2022-01-16 21:17:14]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
int mod;
using namespace std;
int n,m,K;
int s[1010][1010][16],a[16],b[5],tot=0;
int main(){
	scanf("%d%d%d",&K,&n,&m);
	for(int i=1,x1,y1,x2,y2,w;i<=K;i++){
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&w),tot+=w;
		int ty=15;
		if(x1==1&&y1==1) ty^=1;
		if(x1==1&&y2==m) ty^=2;
		if(x2==n&&y1==1) ty^=4;
		if(x2==n&&y2==m) ty^=8;
		s[x1][y1][ty]+=w,s[x1][y2+1][ty]-=w,s[x2+1][y1][ty]-=w,s[x2+1][y2+1][ty]+=w;
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<16;k++){
		s[i][j][k]=s[i][j][k]+s[i-1][j][k]+s[i][j-1][k]-s[i-1][j-1][k];
	}
	b[4]=-1;
	ll ans=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		ll res=0,sum=0;
		for(int k=0;k<16;k++) sum+=(a[k]=s[i][j][k]);
		res=(tot-sum)*(tot-sum-1)/2;
		for(int _=0;_<4;_++){
			int p=4;
			for(int t=0;t<4;t++){
				b[t]=0;
				for(int k=0;k<16;k++) if((k>>t)&1) b[t]+=a[k];
				if(b[t]>=b[p]) p=t;
			}
			res+=b[p]*(b[p]-1ll)/2;
			for(int k=0;k<16;k++) if((k>>p)&1) a[k]=0;
		}
		ans=max(res,ans);
	}
	printf("%lld\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3772kb

input:

2 1 2
1 1 1 1 3
1 2 1 2 4

output:

9

result:

ok answer is '9'

Test #2:

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

input:

3 7 3
1 1 3 3 1
5 1 7 3 1
3 2 5 3 1

output:

3

result:

ok answer is '3'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

1 1 2
1 2 1 2 1

output:

0

result:

ok answer is '0'

Test #4:

score: 0
Accepted
time: 3ms
memory: 5748kb

input:

3 4 1
1 1 2 1 2
4 1 4 1 2
2 1 3 1 1

output:

6

result:

ok answer is '6'

Test #5:

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

input:

5 4 1
1 1 1 1 3
3 1 4 1 1
2 1 4 1 3
1 1 1 1 3
1 1 2 1 1

output:

27

result:

ok answer is '27'

Test #6:

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

input:

4 1 3
1 1 1 1 1
1 2 1 3 5
1 3 1 3 4
1 3 1 3 2

output:

55

result:

ok answer is '55'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

25 5 5
5 3 5 3 5
2 1 3 3 1
3 2 5 5 5
3 3 4 5 4
4 1 5 3 3
2 3 5 3 4
2 2 2 5 2
2 1 5 5 1
1 1 1 4 5
1 2 4 4 3
1 1 2 5 5
1 3 1 5 2
1 5 4 5 1
4 3 4 4 4
2 3 2 5 4
2 2 5 3 1
1 5 3 5 2
2 1 3 5 1
2 2 5 5 5
3 1 5 2 5
3 2 5 5 3
2 3 4 3 5
1 2 5 2 2
2 3 3 4 3
1 4 2 4 1

output:

2374

result:

ok answer is '2374'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

18 1 9
1 1 1 3 3
1 8 1 8 5
1 1 1 7 1
1 8 1 9 5
1 5 1 7 2
1 5 1 9 4
1 8 1 8 3
1 4 1 7 1
1 5 1 5 1
1 1 1 5 3
1 9 1 9 4
1 9 1 9 3
1 2 1 7 1
1 4 1 9 1
1 8 1 9 5
1 4 1 5 1
1 1 1 2 3
1 2 1 7 1

output:

739

result:

ok answer is '739'

Test #9:

score: 0
Accepted
time: 54ms
memory: 66408kb

input:

1 991 954
594 323 932 326 373

output:

69378

result:

ok answer is '69378'

Test #10:

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

input:

91136 1 2
1 2 1 2 693
1 1 1 1 5
1 1 1 1 783
1 1 1 1 126
1 1 1 1 962
1 2 1 2 36
1 2 1 2 90
1 2 1 2 247
1 1 1 1 741
1 1 1 1 817
1 1 1 1 358
1 2 1 2 474
1 1 1 1 763
1 2 1 2 28
1 1 1 1 228
1 2 1 2 182
1 1 1 1 839
1 1 1 1 302
1 1 1 1 174
1 1 1 1 23
1 1 1 1 962
1 1 1 1 968
1 1 1 1 897
1 2 1 2 86
1 2 1 2 2...

output:

519539085736087

result:

ok answer is '519539085736087'

Test #11:

score: 0
Accepted
time: 36ms
memory: 37776kb

input:

59218 829 278
732 7 786 196 1
86 104 531 125 1
220 128 351 227 1
126 69 803 97 1
11 59 487 200 1
363 174 452 191 1
225 151 309 266 1
20 75 69 227 1
537 156 600 164 1
120 150 469 278 1
49 47 639 142 1
63 146 726 264 1
479 188 731 235 1
386 8 758 229 1
132 72 565 169 1
503 18 569 209 1
88 122 192 137 ...

output:

1753356153

result:

ok answer is '1753356153'

Test #12:

score: 0
Accepted
time: 42ms
memory: 47384kb

input:

13144 739 806
63 238 84 776 655
420 113 611 417 558
626 429 667 466 450
274 471 718 558 843
128 599 703 778 652
330 604 666 757 603
478 554 695 619 828
103 340 157 626 664
290 571 714 779 640
292 133 294 506 107
450 58 552 499 259
173 92 565 431 747
367 73 488 433 166
129 96 356 804 475
55 105 570 4...

output:

21892043427535

result:

ok answer is '21892043427535'

Test #13:

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

input:

100000 124 132
1 52 124 132 675
1 1 124 118 180
1 1 8 132 630
1 116 124 132 621
1 3 124 132 436
1 1 124 106 339
82 1 124 132 234
1 120 124 132 10
1 1 59 132 392
1 1 124 57 800
1 1 124 48 931
66 1 124 132 41
1 1 124 64 356
1 128 124 132 292
1 1 124 2 939
1 1 40 132 719
1 66 124 132 440
2 1 124 132 77...

output:

628140784737973

result:

ok answer is '628140784737973'

Test #14:

score: 0
Accepted
time: 44ms
memory: 6548kb

input:

100000 42 1000
1 1 13 1000 773
1 1 42 826 356
1 1 18 1000 345
1 1 10 1000 767
20 1 42 1000 460
1 1 42 534 271
1 1 13 1000 303
1 824 42 1000 200
15 1 42 1000 973
1 1 42 121 794
1 1 7 1000 225
1 567 42 1000 630
1 1 42 560 310
1 33 42 1000 608
1 1 42 767 982
23 1 42 1000 351
1 1 41 1000 18
40 1 42 1000...

output:

627596329603412

result:

ok answer is '627596329603412'

Test #15:

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

input:

100000 1000 31
1 20 1000 31 215
1 1 1000 6 291
1 1 781 31 40
1 1 671 31 564
1 18 1000 31 582
1 1 1000 12 250
1 20 1000 31 787
1 1 1000 12 383
91 1 1000 31 990
1 1 521 31 217
351 1 1000 31 338
1 31 1000 31 52
1 19 1000 31 742
1 23 1000 31 154
1 1 1000 13 399
1 1 550 31 284
1 26 1000 31 681
636 1 1000...

output:

630412995680811

result:

ok answer is '630412995680811'

Test #16:

score: 0
Accepted
time: 101ms
memory: 66960kb

input:

100000 1000 1000
1 233 1000 1000 482
636 1 1000 1000 695
1 1 762 1000 415
961 1 1000 1000 977
1 1 873 1000 522
1 1 919 1000 331
1 1 318 1000 749
1 1 1000 999 289
1 1 139 1000 94
1 835 1000 1000 192
1 1 453 1000 675
1 1 1000 684 964
1 1 1000 165 93
1 1 578 1000 773
1 1 719 1000 521
170 1 1000 1000 55...

output:

623208457894502

result:

ok answer is '623208457894502'

Test #17:

score: 0
Accepted
time: 70ms
memory: 67280kb

input:

1234 1000 1000
795 1 1000 1000 622
1 781 1000 1000 329
1 1 1000 31 761
1 785 1000 1000 650
27 92 79 779 355
222 1 1000 1000 393
822 1 1000 192 210
1 1 333 1000 321
916 1 1000 1000 776
1 42 1000 1000 332
1 1 1000 323 473
1 1 344 1000 14
511 1 1000 1000 126
1 513 1000 1000 452
1 1 821 1000 428
1 140 1...

output:

106889176640

result:

ok answer is '106889176640'

Test #18:

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

input:

100000 10 1000
1 1 10 115 110
1 1 10 23 931
3 1 10 1000 342
1 1 1 874 623
1 1 10 374 839
1 1 9 1000 717
1 579 10 1000 50
1 1 10 263 178
10 1 10 1000 349
1 1 10 509 550
7 735 10 1000 313
1 62 10 1000 949
1 361 10 1000 533
1 333 10 1000 366
1 1 6 1000 542
1 1 1 1000 671
1 185 10 1000 688
9 299 9 874 8...

output:

719610887542416

result:

ok answer is '719610887542416'

Test #19:

score: 0
Accepted
time: 39ms
memory: 36192kb

input:

100000 1000 142
1 1 301 142 40
250 1 724 12 967
713 1 1000 142 382
1 1 456 142 834
1 1 669 142 714
1 1 575 142 953
1 1 1000 65 546
1 1 501 118 659
1 81 1000 142 558
371 1 1000 142 664
1 1 791 111 717
1 1 1000 52 138
1 99 422 111 878
1 1 1000 82 341
509 1 1000 142 532
824 18 855 35 226
1 107 1000 142...

output:

676000785359343

result:

ok answer is '676000785359343'

Test #20:

score: 0
Accepted
time: 106ms
memory: 67132kb

input:

100000 1000 1000
1 1 1000 144 445
390 583 1000 940 725
1 1 233 1000 351
1 1 1000 315 832
488 795 1000 821 289
1 662 1000 1000 250
333 633 791 639 659
858 1 1000 1000 616
1 1 1000 436 891
1 1 1000 555 145
359 419 1000 796 889
1 995 1000 1000 475
1 713 1000 1000 435
197 318 284 596 102
894 1 1000 1000...

output:

669584618287848

result:

ok answer is '669584618287848'

Test #21:

score: 0
Accepted
time: 91ms
memory: 67284kb

input:

100000 1000 988
858 1 1000 988 436
411 1 1000 988 106
1 1 1000 8 895
262 1 1000 988 272
783 688 1000 831 539
506 76 624 244 158
1 184 1000 988 143
1 1 1000 512 636
56 1 1000 988 769
1 1 1000 359 210
604 1 1000 988 647
510 1 1000 988 695
847 1 1000 988 938
1 1 983 988 264
1 1 838 709 302
1 1 1000 78 ...

output:

765523731303957

result:

ok answer is '765523731303957'

Test #22:

score: 0
Accepted
time: 99ms
memory: 66600kb

input:

100000 985 1000
56 91 134 290 758
1 1 985 692 141
1 168 369 302 759
361 1 985 1000 803
1 1 690 1000 578
399 196 985 1000 931
1 988 985 1000 955
493 1 985 965 864
1 1 975 1000 545
296 1 985 1000 812
55 217 686 252 556
535 1 985 1000 537
1 1 533 1000 884
684 204 685 916 714
650 302 985 1000 52
1 888 6...

output:

656828151050504

result:

ok answer is '656828151050504'

Test #23:

score: 0
Accepted
time: 89ms
memory: 66956kb

input:

100000 1000 1000
1 571 224 1000 79
341 1 1000 749 175
801 1 1000 1000 516
56 883 785 1000 413
1 581 1000 1000 644
1 1 1000 287 375
32 1 1000 1000 157
482 1 1000 1000 662
1 96 1000 1000 955
1 1 1000 247 201
1 1 168 1000 478
1 435 1000 1000 241
1 1 1000 417 10
1 1 1000 485 560
739 1 1000 1000 222
899 ...

output:

680480543965598

result:

ok answer is '680480543965598'

Test #24:

score: 0
Accepted
time: 28ms
memory: 6036kb

input:

100000 10 1000
6 1 10 1000 672
1 1 10 331 804
8 1 10 1000 629
3 1 9 294 654
9 1 10 11 557
1 1 10 582 202
5 597 7 1000 294
6 372 8 1000 74
1 596 10 1000 94
1 470 10 1000 707
2 504 9 729 206
10 517 10 678 996
1 178 10 1000 325
7 1 10 816 447
1 1 2 1000 252
1 1 4 1000 95
1 1 10 6 217
1 381 6 1000 909
1...

output:

795874385198798

result:

ok answer is '795874385198798'

Test #25:

score: 0
Accepted
time: 21ms
memory: 4464kb

input:

100000 10 1000
6 1 10 1000 672
1 1 10 331 804
8 1 10 1000 629
3 1 9 294 654
9 1 10 11 557
1 1 10 582 202
5 597 7 1000 294
6 372 8 1000 74
1 596 10 1000 94
1 470 10 1000 707
2 504 9 729 206
10 517 10 678 996
1 178 10 1000 325
7 1 10 816 447
1 1 2 1000 252
1 1 4 1000 95
1 1 10 6 217
1 381 6 1000 909
1...

output:

795874356720991

result:

ok answer is '795874356720991'

Test #26:

score: 0
Accepted
time: 28ms
memory: 31120kb

input:

100000 1000 10
1 1 268 10 270
1 1 1000 2 670
1 1 1000 6 999
99 1 1000 5 179
775 3 917 7 835
1 1 101 10 242
72 4 939 10 659
1 1 409 10 676
1 1 827 9 962
1 1 1000 3 830
1 1 1000 5 852
573 1 1000 10 692
1 3 176 8 994
1 1 1000 6 610
733 5 961 7 240
387 1 1000 10 699
1 1 1000 3 247
1 1 11 10 749
1 1 152 ...

output:

808203815747248

result:

ok answer is '808203815747248'

Test #27:

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

input:

100000 1000 10
1 1 268 10 270
1 1 1000 2 670
1 1 1000 6 999
99 1 1000 5 179
775 3 917 7 835
1 1 101 10 242
72 4 939 10 659
1 1 409 10 676
1 1 827 9 962
1 1 1000 3 830
1 1 1000 5 852
573 1 1000 10 692
1 3 176 8 994
1 1 1000 6 610
733 5 961 7 240
387 1 1000 10 699
1 1 1000 3 247
1 1 11 10 749
1 1 152 ...

output:

808203826364029

result:

ok answer is '808203826364029'

Test #28:

score: 0
Accepted
time: 90ms
memory: 64188kb

input:

100000 958 943
1 775 958 943 848
1 759 958 943 665
1 1 52 943 642
627 1 958 943 684
56 380 177 488 209
212 1 958 912 196
2 1 958 451 251
1 289 780 943 67
296 338 801 792 864
374 1 958 943 179
1 775 958 943 199
1 1 300 725 609
1 1 373 943 988
1 826 958 943 97
1 1 112 943 559
206 384 888 504 406
120 1...

output:

837679174760917

result:

ok answer is '837679174760917'

Test #29:

score: 0
Accepted
time: 87ms
memory: 65500kb

input:

100000 958 943
1 775 958 943 848
1 759 958 943 665
1 1 52 943 642
627 1 958 943 684
56 380 177 488 209
212 1 958 912 196
2 1 958 451 251
1 289 780 943 67
296 338 801 792 864
374 1 958 943 179
1 775 958 943 199
1 1 300 725 609
1 1 373 943 988
1 826 958 943 97
1 1 112 943 559
206 384 888 504 406
120 1...

output:

837679159964669

result:

ok answer is '837679159964669'

Test #30:

score: 0
Accepted
time: 97ms
memory: 67268kb

input:

100000 1000 1000
1 1 326 923 808
1 714 1000 1000 237
653 1 1000 1000 557
804 1 1000 1000 325
1 1 82 1000 549
1 1 280 1000 125
1 302 1000 1000 206
1 1 16 387 47
388 126 462 779 939
793 1 1000 1000 534
1 19 416 434 465
1 124 633 1000 458
950 1 1000 1000 575
1 1 423 1000 368
834 1 1000 1000 328
497 1 1...

output:

820362521785507

result:

ok answer is '820362521785507'

Test #31:

score: 0
Accepted
time: 103ms
memory: 66968kb

input:

100000 1000 1000
1 1 326 923 808
1 714 1000 1000 237
653 1 1000 1000 557
804 1 1000 1000 325
1 1 82 1000 549
1 1 280 1000 125
1 302 1000 1000 206
1 1 16 387 47
388 126 462 779 939
793 1 1000 1000 534
1 19 416 434 465
1 124 633 1000 458
950 1 1000 1000 575
1 1 423 1000 368
834 1 1000 1000 328
497 1 1...

output:

820362534192457

result:

ok answer is '820362534192457'

Test #32:

score: 0
Accepted
time: 7ms
memory: 22644kb

input:

2000 300 300
2 1 300 300 940
1 71 300 300 3
279 1 300 259 18
1 144 300 300 1
1 1 77 300 858
54 1 300 300 605
1 1 177 300 5
1 262 300 300 998
1 1 300 149 892
1 1 283 300 1
1 1 11 300 440
1 1 300 106 1000
1 250 300 300 875
1 108 126 173 418
5 1 222 280 762
129 1 300 300 77
1 103 46 300 588
1 262 300 3...

output:

242972862995

result:

ok answer is '242972862995'

Test #33:

score: 0
Accepted
time: 98ms
memory: 67044kb

input:

100000 1000 1000
941 1 1000 1000 230
35 331 49 1000 438
244 583 1000 736 593
331 1 1000 1000 460
339 367 1000 510 102
1 521 720 601 873
1 1 1000 755 81
1 1 134 1000 576
496 1 1000 1000 345
1 1 1000 182 977
102 1 969 993 564
1 1 82 1000 973
1 423 106 1000 52
544 1 1000 1000 232
1 1 550 736 15
1 1 100...

output:

718543957809609

result:

ok answer is '718543957809609'

Test #34:

score: 0
Accepted
time: 100ms
memory: 66880kb

input:

100000 1000 1000
1 1 352 1000 996
1 1 799 1000 620
1 232 1000 1000 17
1 1 182 1000 883
759 471 865 868 974
1 1 439 1000 180
1 1 1000 430 358
1 674 1000 1000 82
561 88 815 190 456
1 194 1000 1000 798
1 1 1000 617 343
331 614 1000 841 115
424 658 661 1000 515
523 1 1000 1000 923
319 369 915 948 578
1 ...

output:

713098817302784

result:

ok answer is '713098817302784'

Test #35:

score: 0
Accepted
time: 116ms
memory: 66940kb

input:

100000 1000 1000
526 1 1000 689 759
1 280 1000 1000 195
1 1 776 1000 244
1 611 1000 1000 97
9 1 1000 1000 164
917 1 1000 1000 627
1 544 1000 1000 974
673 1 1000 1000 976
1 546 1000 1000 977
1 1 91 1000 450
33 1 765 483 839
1 1 1000 435 153
1 1 580 1000 599
180 1 1000 1000 422
1 1 1000 381 969
1 1 10...

output:

784549544397371

result:

ok answer is '784549544397371'

Test #36:

score: 0
Accepted
time: 101ms
memory: 66924kb

input:

100000 1000 1000
771 1 1000 1000 959
1 1 261 1000 653
920 1 1000 1000 94
483 964 1000 1000 375
284 293 1000 1000 851
480 1 936 540 879
1 248 1000 1000 132
694 143 1000 724 950
1 19 1000 1000 6
1 1 699 1000 956
1 686 1000 1000 846
760 1 1000 1000 961
1 1 1000 773 15
1 931 1000 1000 992
1 1 1000 597 2...

output:

1117586556115351

result:

ok answer is '1117586556115351'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

8 2 2
1 1 1 2 1
1 1 1 2 1
1 1 1 2 1
1 1 1 2 1
1 1 1 2 1
1 1 2 1 20
2 1 2 2 20
1 2 2 2 20

output:

1080

result:

ok answer is '1080'