ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203229 | #2447. C | hegm | 100 | 1224ms | 5060kb | C++11 | 863b | 2024-02-21 08:52:30 | 2024-02-21 12:10:01 |
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define make make_pair
#define N 500005
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;
}
int n,x,y,s[N],cnt=1,ans;
priority_queue<int>q;
signed main()
{
n=read();x=read();y=read();
for(int i=1;i<=n;i++)s[i]=read();
for(int i=1;i<=n;i++)
{
int a=s[i]/y-(s[i]%y==0);//可以得到的次数
int b=s[i]%y+(s[i]%y==0)*y;//剩余的权值
int c=b/x+(b%x!=0);//得分的花费
cnt+=a;
if(cnt>=c)
{
q.push(c);
cnt-=c;ans++;
}
else
{
if(q.size()&&q.top()>c)
{
cnt+=q.top()-c;
q.pop();
q.push(c);
}
cnt++;
}
}
cout<<ans<<"\n";
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 0ms
memory: 1220kb
input:
5 1 2 1 3 1 5 5
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 1216kb
input:
5 3 3 2 4 3 5 3
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 1216kb
input:
5 1 1 1 1 5 3 5
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 0ms
memory: 1220kb
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: 1220kb
input:
5 2 2 1 5 4 2 2
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 1ms
memory: 1216kb
input:
5 3 1 2 3 5 3 2
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 0ms
memory: 1216kb
input:
5 3 3 5 2 2 1 1
output:
3
result:
ok single line: '3'
Test #9:
score: 0
Accepted
time: 0ms
memory: 1216kb
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: 1220kb
input:
5 1 3 1 1 1 1 5
output:
3
result:
ok single line: '3'
Test #12:
score: 0
Accepted
time: 0ms
memory: 1216kb
input:
5 2 1 5 2 5 3 4
output:
5
result:
ok single line: '5'
Test #13:
score: 0
Accepted
time: 0ms
memory: 1216kb
input:
5 1 2 3 5 3 1 5
output:
5
result:
ok single line: '5'
Test #14:
score: 0
Accepted
time: 0ms
memory: 1216kb
input:
5 2 3 5 5 1 2 1
output:
4
result:
ok single line: '4'
Test #15:
score: 0
Accepted
time: 1ms
memory: 1216kb
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: 1224kb
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: 1ms
memory: 1224kb
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: 1ms
memory: 1224kb
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: 1220kb
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: 1224kb
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: 1ms
memory: 1224kb
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: 1220kb
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: 1220kb
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: 1224kb
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: 1224kb
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: 1220kb
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: 1220kb
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: 1224kb
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: 1224kb
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: 11ms
memory: 4008kb
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: 10ms
memory: 4008kb
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: 54ms
memory: 4008kb
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: 50ms
memory: 5056kb
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: 39ms
memory: 5056kb
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: 49ms
memory: 5056kb
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: 50ms
memory: 5060kb
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: 43ms
memory: 5056kb
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: 33ms
memory: 4008kb
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: 47ms
memory: 4008kb
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: 50ms
memory: 4012kb
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: 38ms
memory: 5060kb
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: 45ms
memory: 5060kb
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: 48ms
memory: 4012kb
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: 60ms
memory: 4264kb
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: 58ms
memory: 5056kb
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: 46ms
memory: 3620kb
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: 32ms
memory: 3296kb
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: 51ms
memory: 4008kb
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: 40ms
memory: 5060kb
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: 55ms
memory: 4012kb
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: 38ms
memory: 5060kb
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: 51ms
memory: 4008kb
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: 47ms
memory: 3616kb
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: 34ms
memory: 5056kb
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: 51ms
memory: 5060kb
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: 47ms
memory: 5056kb
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: 42ms
memory: 4012kb
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