QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314022 | #836. Farm of Monsters | AFewSuns | WA | 17ms | 14388kb | C++14 | 1.8kb | 2024-01-25 11:21:00 | 2024-01-25 11:21:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
priority_queue<ll> q;
ll n,A,B,h[300030],a[300030],b[300030];
int main(){
n=read();
A=read();
B=read();
fr(i,1,n) h[i]=read();
fr(i,1,n) a[i]=((h[i]-1)%B+1+A-1)/A;
fr(i,1,n) b[i]=(h[i]+B-1)/B;
ll sum=0,ans=0;
fr(i,1,n){
if((sum+b[i]-1-a[i])>=-1){
sum+=b[i]-1-a[i];
q.push(a[i]+1);
ans++;
}
else if(!q.empty()){
ll u=q.top();
if((u+b[i]-1-a[i])>0){
sum+=u+b[i]-1-a[i];
q.pop();
q.push(a[i]+1);
}
else sum+=b[i];
}
}
write(ans);
}
/*
10 34 100
17 27 73 17 60 12 25 53 31 46
ans:
5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3488kb
input:
3 1 1 1 1 1
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
3 1 1 2 2 2
output:
3
result:
ok answer is '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
10 34 100 17 27 73 17 60 12 25 53 31 46
output:
5
result:
ok answer is '5'
Test #4:
score: 0
Accepted
time: 6ms
memory: 14204kb
input:
300000 1 1 336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 5272...
output:
300000
result:
ok answer is '300000'
Test #5:
score: 0
Accepted
time: 17ms
memory: 14252kb
input:
300000 1 2 75475634 804928248 476927808 284875072 503158867 627937890 322595515 786026685 645468307 669240390 939887597 588586447 973764525 521365644 710156469 985188306 860350786 11308832 784695957 770562147 208427221 35937909 67590963 726478310 475357775 255361535 135993561 166967811 46718075 8515...
output:
300000
result:
ok answer is '300000'
Test #6:
score: 0
Accepted
time: 14ms
memory: 14312kb
input:
300000 1 2 374288891 535590429 751244358 124321145 232930851 266089174 543529670 773363571 319728747 580543238 582720391 468188689 490702144 598813561 138628383 284660056 733781508 155605777 931759705 245485733 723534730 257812292 794937524 596788519 188451996 981010588 14483682 59267682 959461493 3...
output:
300000
result:
ok answer is '300000'
Test #7:
score: 0
Accepted
time: 10ms
memory: 14336kb
input:
300000 1 3 673102149 561219907 730593611 814024114 812959730 314305867 469496529 350635050 699021890 342102981 815487777 787982418 857896659 526518374 421876106 438907614 902179526 449645826 783856158 865633510 238642240 774653971 962475573 467098727 196513513 561435449 333165290 951567552 726980720...
output:
300000
result:
ok answer is '300000'
Test #8:
score: 0
Accepted
time: 13ms
memory: 14308kb
input:
300000 1 4 412106895 291882089 564718673 358502890 837699009 657489855 690430685 632939232 373282330 398630021 753287868 667584659 79866982 603966291 850348020 738379364 480642952 593942770 930919906 485781288 903492853 141752547 984789430 897217447 909607734 846893014 211655411 843867422 789467242 ...
output:
300000
result:
ok answer is '300000'
Test #9:
score: 0
Accepted
time: 14ms
memory: 14260kb
input:
300000 2 5 5887448 757703054 544067926 902981667 712695184 295641139 911364840 620276118 902318577 865222469 250896470 987378388 742028793 681414208 133595743 597659626 649040970 33207011 223207847 960704874 418600362 658594226 417168695 767527655 622701955 867509363 235369723 31134588 702210660 439...
output:
300000
result:
ok answer is '300000'
Test #10:
score: 0
Accepted
time: 8ms
memory: 14252kb
input:
300000 3 4 449924898 783332532 378192988 592684636 147499872 343857831 837331700 197547597 576579017 776525316 188696560 12204822 669031820 758862125 826908873 897131377 817438988 737312468 370271596 580852652 638740575 585501313 439482552 637837864 335796176 447934224 259084035 778210267 469729886 ...
output:
300000
result:
ok answer is '300000'
Test #11:
score: 0
Accepted
time: 8ms
memory: 14248kb
input:
300000 3 3 43705451 513994713 652509537 432130709 317463343 687041819 58265855 479851779 250839457 538085060 126496650 186774359 331193631 836310042 255380788 756411639 690869710 176576709 222368048 906033133 8623893 807375696 461796409 362923880 194114590 733391789 137574156 670510137 237249112 673...
output:
300000
result:
ok answer is '300000'
Test #12:
score: 0
Accepted
time: 10ms
memory: 14388kb
input:
300000 3 9 782710197 539624191 631858791 976609486 752268030 30225807 279200011 467188665 630132600 594612100 769329445 916633496 258196658 913757959 538628510 55883389 859267729 615840950 514655989 526180911 523731402 324217375 189142970 643299496 907208811 754008138 161288468 562810007 149992530 9...
output:
300000
result:
ok answer is '300000'
Test #13:
score: 0
Accepted
time: 12ms
memory: 14272kb
input:
300000 8 8 640274071 983359971 71550121 96204862 799843967 446173607 796619138 402690754 223219513 668171337 312183499 905549873 673542337 566661387 879397647 434495917 631413076 150918417 579868000 224422012 126195703 525305826 535526356 404334728 653535984 998133227 879226371 59632864 356493387 62...
output:
300000
result:
ok answer is '300000'
Test #14:
score: 0
Accepted
time: 14ms
memory: 14312kb
input:
300000 4 20 509061481 552472140 16115810 148658854 66743034 628305150 677780684 519361360 208050516 401554301 954478790 346543678 387546138 832279893 641889899 80960260 717802881 588066499 661699500 83254572 759454419 427833657 255743179 199661234 694729965 875591136 862937826 103626886 473906880 20...
output:
300000
result:
ok answer is '300000'
Test #15:
score: 0
Accepted
time: 14ms
memory: 14352kb
input:
300000 15 31 235040736 845224325 405102476 306020832 567954026 319923972 351391400 839247099 872095141 746927386 116079799 814749285 935104039 39200818 779623552 24872203 857355273 463838168 642352783 774850365 394389351 835930945 10847154 880608047 403727586 922549184 104520573 235608953 266338849 ...
output:
300000
result:
ok answer is '300000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 1 1 5
output:
1
result:
ok answer is '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 1 2 2
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
1 2 1 2
output:
1
result:
ok answer is '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
1 7 9 3
output:
1
result:
ok answer is '1'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
1 7 3 9
output:
1
result:
ok answer is '1'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
1 7 51 50
output:
0
result:
ok answer is '0'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
1 79 51 96
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 60 820 533
output:
0
result:
ok answer is '0'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
1 664 188 495
output:
1
result:
ok answer is '1'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1 297208 929600 614363
output:
0
result:
ok answer is '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
1 589156 45728 619108
output:
1
result:
ok answer is '1'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 505899152 526332989 621636272
output:
1
result:
ok answer is '1'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 409449117 374415292 920449529
output:
1
result:
ok answer is '1'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 1 1 1 1
output:
1
result:
ok answer is '1'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
2 1 1 3 1
output:
2
result:
ok answer is '2'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
2 1 1 2 1
output:
2
result:
ok answer is '2'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 2 1 2 1
output:
2
result:
ok answer is '2'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 5 6 9 9
output:
2
result:
ok answer is '2'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
2 10 9 1 7
output:
1
result:
ok answer is '1'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
2 4 77 3 29
output:
1
result:
ok answer is '1'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 33 29 49 7
output:
2
result:
ok answer is '2'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 982 988 630 233
output:
1
result:
ok answer is '1'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 833 406 183 414
output:
2
result:
ok answer is '2'
Test #40:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
2 311557 743280 610538 535909
output:
0
result:
wrong answer expected '1', found '0'