UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203239#2447. Caugury1001318ms3108kbC++11682b2024-02-21 10:21:162024-02-21 12:10:46

answer

#include <bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch = getchar();}
	while(ch>='0'&&ch<='9'){x = x*10+ch-'0';ch = getchar();}
	return x*f;
}
const int N = 5e5+5;
int a;
int n,x,y,ans;
priority_queue<int>q;
int main(){
	n = read();x = read();y = read();
	int res = 1;
	for(int i=1;i<=n;i++){
		a = read();
		int A = (a-1)/y;
		int B = a-A*y;
		int C = B/x+(B%x!=0);
		res+=A;
		if(res>=C){
			res-=C;
			ans++;
			q.push(C);
		}else{
			if(!q.empty()&&q.top()>C){
				res+=q.top()-C;
				q.pop();
				q.push(C);
			}
			res++; 
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 15
Accepted

Test #1:

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

input:

5 1 2
1 3 1 5 5

output:

4

result:

ok single line: '4'

Test #2:

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

input:

5 3 3
2 4 3 5 3

output:

4

result:

ok single line: '4'

Test #3:

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

input:

5 1 1
1 1 5 3 5

output:

4

result:

ok single line: '4'

Test #4:

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

input:

5 3 2
5 1 1 4 3

output:

5

result:

ok single line: '5'

Test #5:

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

input:

5 1 3
2 5 5 1 2

output:

3

result:

ok single line: '3'

Test #6:

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

input:

5 2 2
1 5 4 2 2

output:

4

result:

ok single line: '4'

Test #7:

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

input:

5 3 1
2 3 5 3 2

output:

5

result:

ok single line: '5'

Test #8:

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

input:

5 3 3
5 2 2 1 1

output:

3

result:

ok single line: '3'

Test #9:

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

input:

5 3 2
5 5 4 4 2

output:

5

result:

ok single line: '5'

Test #10:

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

input:

5 2 3
4 5 1 3 3

output:

3

result:

ok single line: '3'

Test #11:

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

input:

5 1 3
1 1 1 1 5

output:

3

result:

ok single line: '3'

Test #12:

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

input:

5 2 1
5 2 5 3 4

output:

5

result:

ok single line: '5'

Test #13:

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

input:

5 1 2
3 5 3 1 5

output:

5

result:

ok single line: '5'

Test #14:

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

input:

5 2 3
5 5 1 2 1

output:

4

result:

ok single line: '4'

Test #15:

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

input:

5 3 2
1 4 1 2 5

output:

4

result:

ok single line: '4'

Subtask #2:

score: 35
Accepted

Test #16:

score: 35
Accepted
time: 0ms
memory: 1216kb

input:

100 30746116 94983162
752498 36176995 10447497 17314385 35612649 11644645 47662989 44684700 10668280...

output:

50

result:

ok single line: '50'

Test #17:

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

input:

100 18046958 44128786
50717632 56381523 17367956 71252835 6417821 78481859 69982902 98491477 2701183...

output:

73

result:

ok single line: '73'

Test #18:

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

input:

100 4479777 1015025
169458841 4512921 176237531 64805683 75228120 126851899 25528924 80567545 398608...

output:

100

result:

ok single line: '100'

Test #19:

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

input:

100 16687407 93638529
188842281 329254419 375262223 289224000 70805883 107901281 242001020 309938198...

output:

80

result:

ok single line: '80'

Test #20:

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

input:

100 7816690 24884800
28286566 31137751 39896540 3464446 5676003 9176798 7247329 47622567 20653970 15...

output:

61

result:

ok single line: '61'

Test #21:

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

input:

100 1446133 90832592
85295648 25355141 70071737 983288 29012844 95605066 54757831 52979883 79138959 ...

output:

19

result:

ok single line: '19'

Test #22:

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

input:

100 752244 93684880
107113559 108640384 165904132 45287893 53979467 114663402 187623289 153688482 13...

output:

21

result:

ok single line: '21'

Test #23:

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

input:

100 1106201 51897466
235094233 191975275 74636892 62181264 3357612 454642346 303176747 38766918 8462...

output:

42

result:

ok single line: '42'

Test #24:

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

input:

100 391413 14391614
7460128 19077095 46376766 5412083 47523982 27653341 34030361 78350 48014508 2263...

output:

35

result:

ok single line: '35'

Test #25:

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

input:

100 764668 99832223
99655530 20466570 49915106 73870932 46265310 81498930 80244448 19967711 91243404...

output:

8

result:

ok single line: '8'

Test #26:

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

input:

100 897157 40767246
3472920 23825698 71109207 36016787 9811282 173788793 65025819 22936468 77516161 ...

output:

29

result:

ok single line: '29'

Test #27:

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

input:

100 23086792 26777808
56879103 61148104 27321308 59715125 92651182 81136570 88568748 47765094 652291...

output:

100

result:

ok single line: '100'

Test #28:

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

input:

100 40704 64835460
186969419 268760362 16162269 285997906 418487688 260767896 29983041 381409969 320...

output:

5

result:

ok single line: '5'

Test #29:

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

input:

100 57628372 32876567
141983530 161496348 117604684 40620964 123936568 23112226 175079795 153184105 ...

output:

100

result:

ok single line: '100'

Test #30:

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

input:

100 6971060 90556231
126015437 493162358 336803860 345951519 376035167 467042336 126811093 407177733...

output:

64

result:

ok single line: '64'

Test #31:

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

input:

100 44114320 20411836
20181278 1079964 29712128 33838884 32099455 4420169 25177978 6233349 23419207 ...

output:

87

result:

ok single line: '87'

Test #32:

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

input:

100 10992354 33888279
31381834 98926331 57764293 9332847 68321042 59967301 41066396 70220629 9465475...

output:

74

result:

ok single line: '74'

Test #33:

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

input:

100 17931379 93820371
17540815 138518756 160905757 37032437 43888780 188985989 169684132 52465027 66...

output:

59

result:

ok single line: '59'

Test #34:

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

input:

100 17005978 25057322
369616665 361357321 42900519 230944541 73959286 186083141 344701957 24983160 6...

output:

100

result:

ok single line: '100'

Test #35:

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

input:

100 10141624 39561002
22438880 27871926 23923324 27744576 41208910 21381829 3590359 25645174 9298303...

output:

54

result:

ok single line: '54'

Subtask #3:

score: 3
Accepted

Test #36:

score: 3
Accepted
time: 10ms
memory: 2056kb

input:

499997 820789271 552941815
1 1 1 1 1 1 1 1 1 1 1 1 1 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:

249999

result:

ok single line: '249999'

Test #37:

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

input:

500000 539815474 548787075
1 1 1 1 1 1 1 1 1 1 1 1 1 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:

250000

result:

ok single line: '250000'

Subtask #4:

score: 22
Accepted

Test #38:

score: 22
Accepted
time: 59ms
memory: 2060kb

input:

500000 60629748 500000000
17969125 325845453 404269876 233244808 238539120 297619623 502418390 88245...

output:

233735

result:

ok single line: '233735'

Test #39:

score: 0
Accepted
time: 53ms
memory: 3104kb

input:

500000 467392842 500000000
619893245 332484831 493641552 674500752 611900345 505915826 858016704 111...

output:

366047

result:

ok single line: '366047'

Test #40:

score: 0
Accepted
time: 53ms
memory: 3104kb

input:

500000 273050451 300000000
275531670 877786394 423820488 718218928 750085477 697571893 31194153 8145...

output:

499997

result:

ok single line: '499997'

Test #41:

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

input:

500000 134391226 300000000
734001834 68663156 20938275 804836652 383643842 279004148 238582204 97535...

output:

442821

result:

ok single line: '442821'

Test #42:

score: 0
Accepted
time: 52ms
memory: 3104kb

input:

500000 173891540 300000000
482172803 391176212 67129691 135014640 393575531 560118673 304286932 7325...

output:

461013

result:

ok single line: '461013'

Test #43:

score: 0
Accepted
time: 57ms
memory: 3104kb

input:

500000 117542709 300000000
97626306 292316721 717205759 821462477 430761900 490454718 202310864 1505...

output:

428154

result:

ok single line: '428154'

Subtask #5:

score: 25
Accepted

Test #44:

score: 25
Accepted
time: 47ms
memory: 2056kb

input:

500000 35683572 97458599
34526397 10712548 19740332 5838662 41032574 7190813 8327281 26947240 241970...

output:

250000

result:

ok single line: '250000'

Test #45:

score: 0
Accepted
time: 53ms
memory: 2056kb

input:

500000 11140387 67310881
86932047 8007534 71561989 17417580 4573067 8442459 10150819 32550805 516133...

output:

247262

result:

ok single line: '247262'

Test #46:

score: 0
Accepted
time: 46ms
memory: 2056kb

input:

500000 1877007 61886528
69517097 140797946 160471331 146704408 170691587 79815031 43236084 192834123...

output:

172139

result:

ok single line: '172139'

Test #47:

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

input:

500000 12171490 7108268
411619806 185868818 18560649 358136251 496270639 217669122 357470157 1075477...

output:

500000

result:

ok single line: '500000'

Test #48:

score: 0
Accepted
time: 53ms
memory: 3104kb

input:

500000 7971338 26906364
22222839 46050336 19384980 39448383 24434278 37862185 27583712 6410893 26866...

output:

295124

result:

ok single line: '295124'

Test #49:

score: 0
Accepted
time: 62ms
memory: 2056kb

input:

500000 1562342 39546635
56846309 7179201 4666479 10902469 83826674 40200596 88762681 28744191 801083...

output:

171902

result:

ok single line: '171902'

Test #50:

score: 0
Accepted
time: 61ms
memory: 2316kb

input:

500000 3079879 47161569
36217896 161710858 195646839 51872297 107454639 6152234 157631769 144899141 ...

output:

256622

result:

ok single line: '256622'

Test #51:

score: 0
Accepted
time: 47ms
memory: 3108kb

input:

500000 9766072 67834319
429315759 94554379 24917723 149024711 18382323 270278678 113305376 276774941...

output:

445394

result:

ok single line: '445394'

Test #52:

score: 0
Accepted
time: 43ms
memory: 1668kb

input:

500000 807674 61799642
43854975 22652052 29572488 36804220 5060914 34142858 43680943 18177935 224192...

output:

79153

result:

ok single line: '79153'

Test #53:

score: 0
Accepted
time: 43ms
memory: 1344kb

input:

500000 19347 82631258
22092952 80106552 30355780 11645168 93558754 62569154 25164173 47298612 373029...

output:

14542

result:

ok single line: '14542'

Test #54:

score: 0
Accepted
time: 62ms
memory: 2056kb

input:

500000 642185 37529059
85286676 2369680 56612888 164263443 60372508 132617420 81623240 17388857 1850...

output:

157542

result:

ok single line: '157542'

Test #55:

score: 0
Accepted
time: 48ms
memory: 3104kb

input:

500000 81351960 81468439
85495510 20934514 10217606 21818928 34486071 50279812 10366029 15813535 906...

output:

293064

result:

ok single line: '293064'

Test #56:

score: 0
Accepted
time: 56ms
memory: 2060kb

input:

500000 709545 55190116
133287569 139238081 407855347 440730342 314736261 257415047 43815390 1099166 ...

output:

170470

result:

ok single line: '170470'

Test #57:

score: 0
Accepted
time: 40ms
memory: 3104kb

input:

500000 26445172 19762557
108003598 130550332 189234752 83576125 127570572 60386907 133341092 6906944...

output:

500000

result:

ok single line: '500000'

Test #58:

score: 0
Accepted
time: 55ms
memory: 2060kb

input:

500000 181890 30421716
7454028 479667988 88879057 204612697 363186284 148657456 130568064 201804219 ...

output:

156160

result:

ok single line: '156160'

Test #59:

score: 0
Accepted
time: 43ms
memory: 1664kb

input:

500000 2049096 63461019
18087262 32488793 21587647 8796869 25684405 46195172 725114 10196954 3481150...

output:

116333

result:

ok single line: '116333'

Test #60:

score: 0
Accepted
time: 37ms
memory: 3104kb

input:

500000 14736537 7103603
60594141 6407807 52027706 42196182 2254613 8898742 95940962 61349701 1905538...

output:

500000

result:

ok single line: '500000'

Test #61:

score: 0
Accepted
time: 45ms
memory: 3108kb

input:

500000 35068318 74043655
79238222 130180433 168293507 198782079 61353391 41210115 101928224 13495610...

output:

391890

result:

ok single line: '391890'

Test #62:

score: 0
Accepted
time: 45ms
memory: 3104kb

input:

500000 11150229 61261616
194251653 40626037 452129939 361867793 14101759 460938059 68253146 20575830...

output:

499997

result:

ok single line: '499997'

Test #63:

score: 0
Accepted
time: 48ms
memory: 2060kb

input:

500000 18387929 88586074
4980815 20202290 4943098 47021250 46120704 30630008 40535127 49840283 26586...

output:

229569

result:

ok single line: '229569'

Extra Test:

score: 0
Extra Test Passed