QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55278#1961. PostmanKING_UT#WA 133ms11284kbC++202.0kb2022-10-12 21:46:092022-10-12 21:46:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 21:46:12]
  • 评测
  • 测评结果:WA
  • 用时:133ms
  • 内存:11284kb
  • [2022-10-12 21:46:09]
  • 提交

answer

#include <bits/stdc++.h>
#define SIZE 300005
#define LINF 100000000000000LL
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct pque{
	priority_queue <ll,vector <ll>,greater <ll> > zan;
	priority_queue <ll> tp;
	ll sum;
	int nm;
	
	void init(){
		sum=0;
		nm=0;
		while(!zan.empty()) zan.pop();
		while(!tp.empty()) tp.pop();
	}
	void normalize(){
		while(tp.size()<nm){
			sum+=2LL*zan.top();
			tp.push(zan.top());
			zan.pop();
		}
		while(tp.size()>nm){
			sum-=2LL*tp.top();
			zan.push(tp.top());
			tp.pop();
		}
		while(nm>0&&!zan.empty()&&tp.top()>zan.top()){
			sum-=2LL*tp.top();
			sum+=2LL*zan.top();
			zan.push(tp.top());
			tp.pop();
			tp.push(zan.top());
			zan.pop();
		}
	}
	void add(ll d){
		sum+=d;
		zan.push(d);
		normalize();
	}
	void reset(int nd){
		nm=nd;
		normalize();
	}
};
ll solve(vector <P> vx,int w,int t){
	int n=vx.size();
	sort(vx.begin(),vx.end());
	pque que;
	que.init();
	int cnt=0;
	ll d=0;
	if(vx[0].first<0){
		d=2LL*(-vx[0].first);
	}
	ll ret=LINF;
	bool up=true;
	for(int i=0;i<n;i++){
		if(vx[i].first<0){
			cnt++;
			continue;
		}
		int uu=n-1;
		if(up){
			up=false;
			d+=vx[i].first;
		} else uu--;
		int low=0;
		if(cnt) low++;
		if(i!=n-1) low++;
		if(low<=w&&w<=uu){
			ll cur=d+2LL*(vx[n-1].first-vx[i].first);
			int mx=cnt+(n-i-1);
			que.reset(max(0,w-mx));
			if(t==1) ret=min(ret,que.sum+cur);
			else if(vx[i].second==n-1) ret=min(ret,que.sum+cur);
			//printf("%d %lld : %lld\n",vx[i].first,cur,que.sum);
		}
		if(w==1&&vx[0].first<0&&vx[n-1].first>0&&i<n-1){
			ll cur=2LL*(-vx[0].first)+3LL*vx[i].first+2LL*(vx[n-1].first-vx[i].first);
			if(t==1||vx[i].second==n-1) ret=min(ret,cur);
		}
		if(i+1<n) que.add(vx[i+1].first-vx[i].first);
	}
	//puts("");
	return ret;
}
int main(){
	int n,w,t;
	scanf("%d%d%d",&n,&w,&t);
	vector <P> vx(n);
	for(int i=0;i<n;i++){
		scanf("%d",&vx[i].first);
		vx[i].second=i;
	}
	ll ret=solve(vx,w,t);
	for(int i=0;i<n;i++) vx[i].first=-vx[i].first;
	ret=min(ret,solve(vx,n-w,t));
	printf("%lld\n",ret==LINF?-1:ret);
}

詳細信息

Test #1:

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

input:

100 0 1
751 558 131 292 317 886 785 847 224 668 649 358 725 250 953 65 176 733 461 84 114 977 628 673 798 863 373 827 51 630 518 347 527 876 366 241 452 670 813 314 846 342 357 460 985 581 841 843 282 907 327 656 411 944 421 99 441 388 568 763 167 351 793 916 517 109 999 390 272 639 513 534 304 253 ...

output:

999

result:

ok single line: '999'

Test #2:

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

input:

100 50 1
654 349 533 94 619 754 498 939 469 518 3 661 431 214 195 198 989 548 561 312 262 629 807 981 624 639 178 765 706 782 888 611 553 363 336 91 176 485 735 791 596 455 390 760 995 202 417 82 798 883 209 155 725 908 789 56 49 899 231 423 815 228 314 400 748 946 736 840 385 446 938 284 10 917 593...

output:

1397

result:

ok single line: '1397'

Test #3:

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

input:

100 99 1
266 337 80 671 358 778 217 288 219 48 863 19 137 987 602 415 155 398 753 956 210 317 94 303 997 192 123 442 666 959 685 71 34 588 615 214 327 881 582 51 646 630 291 354 749 108 984 308 813 182 384 699 114 692 611 296 590 432 103 240 341 465 969 370 771 914 250 656 742 708 174 323 939 493 17...

output:

1986

result:

ok single line: '1986'

Test #4:

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

input:

100 100 1
713 172 634 763 181 502 78 995 598 751 792 961 585 335 952 343 375 627 651 515 856 121 743 931 18 492 726 517 136 143 314 993 80 29 283 427 248 274 114 200 535 94 174 782 818 90 806 88 104 808 910 892 791 462 304 676 67 973 901 891 705 567 475 444 949 846 299 735 233 914 803 27 810 210 396...

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

100 0 1
-102 -827 -638 -660 -604 -258 -692 -237 -927 -371 -129 -908 -830 -229 -585 -364 -103 -58 -975 -153 -563 -17 -201 -443 -56 -560 -606 -45 -891 -331 -349 -420 -266 -219 -482 -716 -51 -723 -876 -211 -121 -63 -814 -239 -937 -541 -74 -69 -334 -42 -227 -479 -571 -137 -913 -885 -525 -475 -930 -405 -...

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

100 1 1
-747 -27 -215 -283 -833 -584 -531 -295 -636 -725 -100 -506 -108 -426 -574 -305 -919 -207 -540 -770 -264 -67 -388 -444 -77 -778 -474 -957 -706 -467 -438 -245 -240 -228 -40 -523 -803 -669 -198 -11 -740 -911 -990 -604 -236 -628 -864 -897 -440 -789 -874 -941 -153 -1 -52 -345 -819 -480 -731 -612 ...

output:

1979

result:

ok single line: '1979'

Test #7:

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

input:

100 50 1
-220 -474 -778 -792 -88 -62 -252 -742 -147 -2 -119 -575 -583 -434 -753 -425 -427 -266 -419 -344 -44 -470 -79 -28 -38 -621 -506 -821 -363 -423 -960 -272 -608 -728 -482 -392 -194 -958 -395 -712 -97 -867 -34 -499 -101 -777 -895 -200 -269 -528 -283 -972 -157 -378 -561 -90 -359 -439 -412 -72 -87...

output:

1433

result:

ok single line: '1433'

Test #8:

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

input:

100 100 1
-100 -438 -107 -887 -504 -162 -557 -696 -551 -955 -634 -230 -109 -3 -754 -669 -775 -685 -517 -137 -80 -419 -207 -131 -554 -26 -864 -981 -282 -925 -704 -457 -186 -975 -730 -174 -294 -176 -664 -385 -625 -894 -93 -156 -737 -541 -265 -906 -403 -445 -41 -260 -609 -828 -60 -800 -750 -6 -239 -846...

output:

981

result:

ok single line: '981'

Test #9:

score: 0
Accepted
time: 94ms
memory: 11104kb

input:

300000 299900 1
975494913 919276412 971822415 306295652 981185393 751782065 954706942 908207836 981200361 32580760 933121007 333012429 165323270 996792016 391102892 389040132 322687143 812406210 317257318 897931477 984765477 903680189 380567163 385513860 359332788 768879270 959852716 843574823 40665...

output:

2999995655

result:

ok single line: '2999995655'

Test #10:

score: 0
Accepted
time: 86ms
memory: 11060kb

input:

300000 299998 1
909963807 988052984 968956733 -4808472 902213296 920535913 892118351 827900769 961754681 767948569 999500834 260018295 349443084 916399438 810195269 870433267 998221337 976774994 721697345 309230801 868119413 986186795 839916169 968333430 270886226 972109273 970633299 744019611 94687...

output:

2999982764

result:

ok single line: '2999982764'

Test #11:

score: 0
Accepted
time: 79ms
memory: 11204kb

input:

300000 199998 1
760358089 791244679 984736604 275806750 247939634 978615072 302237434 991049550 934591187 382618436 230786914 789192758 236573159 396652403 855918715 877242673 984062779 458214751 395632321 988479643 399571663 377064418 969391408 796094553 999200405 268953105 991121067 941437116 8161...

output:

2999990891

result:

ok single line: '2999990891'

Test #12:

score: 0
Accepted
time: 82ms
memory: 11284kb

input:

300000 159999 1
942199382 341392725 348398313 975348962 960975251 991959712 53847869 626494403 440799630 834310895 400767959 364210160 292487754 970542288 975196994 411308866 985283714 134051724 395718459 725662488 484999687 920311363 991679253 970656922 988945259 265707789 986990069 925538439 21784...

output:

2999991601

result:

ok single line: '2999991601'

Test #13:

score: 0
Accepted
time: 109ms
memory: 10080kb

input:

300000 19999 1
816144624 978397453 440665138 283612424 945098204 339820332 885340682 313718676 922094581 381702751 471032137 872210762 240663640 985886109 780872483 996469198 325835675 968745840 794294823 121382252 948969054 880827421 977238043 126375169 950327749 994803525 201684720 219097101 41030...

output:

2999973677

result:

ok single line: '2999973677'

Test #14:

score: 0
Accepted
time: 96ms
memory: 11212kb

input:

300000 100 1
-989312886 26761301 -985728917 -391478114 -78077877 -953591083 -952597776 -966592009 -374175692 -972714759 -865102046 -253636908 -864766148 -877082592 -985097949 -955548975 -946513709 -939137884 -856158829 -878136428 -845660452 -236979816 -198429617 -194522362 -881227475 -934250481 -955...

output:

2999995006

result:

ok single line: '2999995006'

Test #15:

score: 0
Accepted
time: 133ms
memory: 11176kb

input:

300000 2 1
-204526971 -679003931 -270259823 -998170158 -517990818 -331521849 -806999125 -884402567 -394558999 -938154172 -881759024 -205775904 -989396335 -323846513 -902520693 -105353949 -989729701 -999109123 -958206886 -306635474 -650621491 -980044442 -238027623 -916877077 -987985082 -888733152 -92...

output:

2999989700

result:

ok single line: '2999989700'

Test #16:

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

input:

300000 100002 1
-982563248 -884271825 -991717692 -66746774 -387604370 -989101502 -921822473 -452835479 -343905539 -982352212 -334927349 -951113204 -975955017 -816967163 -951729538 -694131066 -367658474 -933012591 -276245389 -456156314 -309453648 -818983958 -832001600 -247724435 -401778387 -287758829...

output:

2999985866

result:

ok single line: '2999985866'

Test #17:

score: 0
Accepted
time: 80ms
memory: 10924kb

input:

300000 140001 1
-981316007 -209123045 -183025883 -382483756 -958956835 -981127429 -996221336 -953952589 -904879391 -283899126 -828187571 -206037038 -961803343 -987393716 -953516223 -348983568 -927817660 281748110 -999551602 -96518828 -400608671 31532273 -872389194 -322196531 -852614563 -441246454 -2...

output:

2999993311

result:

ok single line: '2999993311'

Test #18:

score: 0
Accepted
time: 105ms
memory: 11216kb

input:

300000 280001 1
-913709302 -903985908 -940299999 -205921103 -885171614 -92135108 -977947386 -988415908 -320447615 -795241235 -999358836 -984300628 -406654796 -479470316 -415791878 -966100008 -978511377 -301932359 -356529615 -997674923 -876662022 -887931627 -435841697 -996688996 -985518116 -992611953...

output:

2999990077

result:

ok single line: '2999990077'

Test #19:

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

input:

201 0 2
813 958 277 425 585 853 243 463 433 999 890 615 984 992 363 704 962 349 822 629 44 836 3 832 214 127 816 106 560 570 693 40 934 910 310 674 508 930 995 982 761 429 329 283 602 312 190 67 29 531 847 267 480 956 225 592 466 527 343 809 206 633 364 202 951 581 808 460 940 610 821 725 745 846 12...

output:

-1

result:

ok single line: '-1'

Test #20:

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

input:

201 1 2
641 284 624 715 55 416 598 109 896 957 102 777 343 933 263 245 488 444 65 493 860 504 595 98 856 685 358 523 434 882 835 497 785 526 531 272 781 101 535 501 207 510 945 41 214 770 556 314 87 522 361 517 513 815 969 847 919 867 779 333 727 908 811 228 857 4 153 441 198 419 437 515 664 113 394...

output:

1484

result:

ok single line: '1484'

Test #21:

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

input:

201 2 2
459 848 667 178 587 393 240 592 679 43 323 670 473 484 844 988 243 40 644 657 786 870 33 521 183 523 631 696 701 572 281 306 912 886 915 961 549 538 739 941 706 712 820 506 881 916 266 69 860 84 54 677 945 370 773 681 733 800 312 296 50 953 671 794 356 188 190 390 831 542 433 210 398 57 874 ...

output:

1491

result:

ok single line: '1491'

Test #22:

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

input:

201 100 2
325 812 770 920 500 742 868 298 47 240 521 458 250 991 396 413 314 618 11 192 704 188 187 781 948 611 115 360 890 662 373 612 776 479 368 766 108 209 926 799 636 539 701 762 579 455 312 747 306 21 691 687 904 974 852 994 140 380 625 614 347 29 519 571 518 431 543 914 385 791 765 559 617 27...

output:

1514

result:

ok single line: '1514'

Test #23:

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

input:

201 101 2
363 662 422 678 921 302 192 43 813 948 288 849 3 993 119 59 587 56 605 729 265 42 77 281 417 160 832 717 520 150 379 705 415 106 359 759 507 820 15 523 29 826 37 392 864 140 10 997 767 633 204 498 102 467 447 370 736 439 703 685 535 963 646 928 529 33 816 68 7 566 198 831 752 896 651 593 1...

output:

1498

result:

ok single line: '1498'

Test #24:

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

input:

201 0 2
-706 735 631 -970 -867 -945 99 -987 -930 -335 -157 -610 464 -357 -27 988 501 -528 -739 774 -443 540 876 -862 26 -244 344 453 178 -437 295 -95 -812 361 360 -747 889 -842 641 811 226 -776 420 -293 519 718 518 736 -462 617 -215 836 -822 -582 -472 -239 -653 -525 -990 -836 858 -403 308 270 803 -7...

output:

-1

result:

ok single line: '-1'

Test #25:

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

input:

201 1 2
-127 -217 -571 -295 618 -626 871 253 886 -632 131 -863 785 -789 -706 111 -598 -496 -116 -246 -901 -94 -122 322 783 498 -831 247 415 -918 156 -805 94 -18 -319 671 495 -521 -407 595 782 -278 690 -719 -340 552 966 -317 -248 -408 521 217 -497 -971 465 852 798 -397 280 803 -400 -739 -604 980 790 ...

output:

2986

result:

ok single line: '2986'

Test #26:

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

input:

201 5 2
-389 505 -693 -810 804 246 -880 -847 266 145 118 361 289 -457 318 -67 522 -207 -844 343 194 -662 621 90 -253 -242 850 816 211 -824 400 -674 -214 -278 767 -137 161 -229 -917 -621 -571 539 800 -198 129 -922 112 479 724 -461 -631 967 -549 972 -12 30 711 -735 558 21 662 936 -362 -957 892 367 -21...

output:

2969

result:

ok single line: '2969'

Test #27:

score: -100
Wrong Answer
time: 2ms
memory: 3828kb

input:

201 199 2
271 -122 -574 116 -482 942 840 138 -962 -546 800 861 -501 -552 -970 -108 -768 -288 -136 82 -861 -698 843 -177 823 814 -55 -603 -70 489 -275 -427 -401 -788 -859 -317 -904 107 -887 -250 892 -651 666 -778 -7 -210 -588 -566 -669 482 -129 263 789 -468 -110 -13 763 392 740 -274 -469 597 670 -239...

output:

4842

result:

wrong answer 1st lines differ - expected: '4862', found: '4842'