QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #507257 | #5259. Skills in Pills | ucup-team1525# | AC ✓ | 36ms | 27388kb | C++17 | 2.5kb | 2024-08-06 14:43:30 | 2024-08-06 14:43:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int inf=1<<30;
int n,a,b;
struct F{
int c,x;
F(int c=0,int x=0):c(c),x(x){}
bool operator <= (const F t) const{
return c==t.c?x>=t.x:c<t.c;
}
}f[N+5][2];
int q[2][N+5],ql[2],qr[2];
F mn(F x,F y){ return x<=y?x:y; }
int main(){
scanf("%d %d %d",&a,&b,&n);
f[0][0]=f[0][1]=F();
for(int i=0;i<2;i++){
q[i][++ql[i]]=0;
qr[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=0;j<2;j++){
f[i][j]=F(inf,0);
int aa=a,bb=b;
if(j) swap(aa,bb);
while(ql[j]<=qr[j]){
int p=q[j][ql[j]];
if(p<=i-aa||f[p][j].x<i-bb) ql[j]++;
else break;
}
}
for(int j=0;j<2;j++){
int k=j^1,aa=j?b:a;
if(ql[k]<=qr[k]){
int l=ql[k],r=qr[k];
int pl=q[k][l];
while(l<=r){
int mid=l+r>>1;
int p=q[k][mid];
if(f[p][k].c==f[pl][k].c&&f[p][k].x>=i-aa) l=mid+1;
else r=mid-1;
}
int p=q[k][r];
f[i][j]=mn(f[i][j],F(f[p][k].c+1,p));
}
}
for(int j=0;j<2;j++){
int aa=a,bb=b;
if(j) swap(aa,bb);
while(ql[j]<=qr[j]){
int p=q[j][ql[j]];
if(p<=i-aa||f[p][j].x<=i-bb) ql[j]++;
else break;
}
}
for(int j=0;j<2;j++){
int k=j;
if(ql[k]<=qr[k]){
int p=q[k][ql[k]];
// printf("%d %d\n",i,p);
f[i][j]=mn(f[i][j],F(f[p][k].c+1,f[p][k].x));
}
}
if(i>=a&&f[i-a][0].x>i-b)
f[i][0]=mn(f[i][0],F(f[i-a][0].c+1,f[i-a][0].x));
if(i>=b&&f[i-b][1].x>i-a)
f[i][1]=mn(f[i][1],F(f[i-b][1].c+1,f[i-b][1].x));
for(int j=0;j<2;j++){
while(ql[j]<=qr[j]){
int p=q[j][qr[j]];
if(f[i][j]<=f[p][j]) qr[j]--;
else break;
}
q[j][++qr[j]]=i;
// printf("%d %d\n",ql[j],qr[j]);
}
// printf("0 %d %d\n",f[i][0].c,f[i][0].x);
// printf("1 %d %d\n",f[i][1].c,f[i][1].x);
}
int p0=q[0][ql[0]],p1=q[1][ql[1]];
printf("%d\n",min(f[p0][0].c,f[p1][1].c));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 21784kb
input:
3 9 20
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 23416kb
input:
8 2 12
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 5ms
memory: 22292kb
input:
2 5 15
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 0ms
memory: 21640kb
input:
10 8 13
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 22376kb
input:
6 6 19
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 4ms
memory: 22812kb
input:
2 3 5
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 3ms
memory: 22568kb
input:
4 2 8
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 0ms
memory: 23136kb
input:
5 5 5
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 22688kb
input:
3 8 11
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 3ms
memory: 21796kb
input:
5 8 16
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 0ms
memory: 23288kb
input:
9 7 279
output:
70
result:
ok single line: '70'
Test #12:
score: 0
Accepted
time: 0ms
memory: 21652kb
input:
8 3 56
output:
25
result:
ok single line: '25'
Test #13:
score: 0
Accepted
time: 4ms
memory: 23604kb
input:
5 9 46
output:
14
result:
ok single line: '14'
Test #14:
score: 0
Accepted
time: 0ms
memory: 21892kb
input:
8 4 251
output:
93
result:
ok single line: '93'
Test #15:
score: 0
Accepted
time: 5ms
memory: 23160kb
input:
8 7 41
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 22580kb
input:
60 17 360
output:
27
result:
ok single line: '27'
Test #17:
score: 0
Accepted
time: 0ms
memory: 23044kb
input:
16 55 388
output:
31
result:
ok single line: '31'
Test #18:
score: 0
Accepted
time: 0ms
memory: 23360kb
input:
25 38 292
output:
18
result:
ok single line: '18'
Test #19:
score: 0
Accepted
time: 4ms
memory: 23580kb
input:
22 59 177
output:
11
result:
ok single line: '11'
Test #20:
score: 0
Accepted
time: 0ms
memory: 22136kb
input:
4 3 82
output:
50
result:
ok single line: '50'
Test #21:
score: 0
Accepted
time: 19ms
memory: 27384kb
input:
77 18 511543
output:
35070
result:
ok single line: '35070'
Test #22:
score: 0
Accepted
time: 36ms
memory: 27380kb
input:
37 32 987861
output:
57612
result:
ok single line: '57612'
Test #23:
score: 0
Accepted
time: 13ms
memory: 21856kb
input:
29 8 300899
output:
48059
result:
ok single line: '48059'
Test #24:
score: 0
Accepted
time: 24ms
memory: 22848kb
input:
73 83 533839
output:
13745
result:
ok single line: '13745'
Test #25:
score: 0
Accepted
time: 6ms
memory: 23680kb
input:
12 23 181193
output:
23008
result:
ok single line: '23008'
Test #26:
score: 0
Accepted
time: 19ms
memory: 27280kb
input:
2 2 864514
output:
864514
result:
ok single line: '864514'
Test #27:
score: 0
Accepted
time: 3ms
memory: 21876kb
input:
27 7 165249
output:
29765
result:
ok single line: '29765'
Test #28:
score: 0
Accepted
time: 17ms
memory: 27332kb
input:
15 2 751665
output:
429522
result:
ok single line: '429522'
Test #29:
score: 0
Accepted
time: 14ms
memory: 27340kb
input:
2 16 818146
output:
460207
result:
ok single line: '460207'
Test #30:
score: 0
Accepted
time: 22ms
memory: 25292kb
input:
43 88 631366
output:
21860
result:
ok single line: '21860'
Test #31:
score: 0
Accepted
time: 0ms
memory: 22564kb
input:
215 1222 3597
output:
18
result:
ok single line: '18'
Test #32:
score: 0
Accepted
time: 13ms
memory: 23024kb
input:
9619 3375 604892
output:
241
result:
ok single line: '241'
Test #33:
score: 0
Accepted
time: 5ms
memory: 22680kb
input:
861 1924 311511
output:
522
result:
ok single line: '522'
Test #34:
score: 0
Accepted
time: 20ms
memory: 23572kb
input:
9249 3782 866972
output:
322
result:
ok single line: '322'
Test #35:
score: 0
Accepted
time: 6ms
memory: 22724kb
input:
7055 8386 206874
output:
53
result:
ok single line: '53'
Test #36:
score: 0
Accepted
time: 0ms
memory: 21800kb
input:
6273 7732 122377
output:
34
result:
ok single line: '34'
Test #37:
score: 0
Accepted
time: 3ms
memory: 22192kb
input:
8057 7746 89137
output:
22
result:
ok single line: '22'
Test #38:
score: 0
Accepted
time: 0ms
memory: 22664kb
input:
9215 8952 74618
output:
16
result:
ok single line: '16'
Test #39:
score: 0
Accepted
time: 7ms
memory: 22268kb
input:
7246 3709 129579
output:
51
result:
ok single line: '51'
Test #40:
score: 0
Accepted
time: 15ms
memory: 22212kb
input:
4052 6785 831888
output:
327
result:
ok single line: '327'
Test #41:
score: 0
Accepted
time: 3ms
memory: 22832kb
input:
9 2 91067
output:
56916
result:
ok single line: '56916'
Test #42:
score: 0
Accepted
time: 24ms
memory: 27388kb
input:
10 3 913595
output:
406041
result:
ok single line: '406041'
Test #43:
score: 0
Accepted
time: 4ms
memory: 27204kb
input:
2 2 152575
output:
152575
result:
ok single line: '152575'
Test #44:
score: 0
Accepted
time: 22ms
memory: 27212kb
input:
2 2 927771
output:
927771
result:
ok single line: '927771'
Test #45:
score: 0
Accepted
time: 16ms
memory: 22656kb
input:
6 7 637014
output:
200204
result:
ok single line: '200204'
Test #46:
score: 0
Accepted
time: 13ms
memory: 27348kb
input:
5 3 721417
output:
400786
result:
ok single line: '400786'
Test #47:
score: 0
Accepted
time: 6ms
memory: 25784kb
input:
5 9 183079
output:
57538
result:
ok single line: '57538'
Test #48:
score: 0
Accepted
time: 12ms
memory: 27324kb
input:
9 2 579290
output:
362055
result:
ok single line: '362055'
Test #49:
score: 0
Accepted
time: 17ms
memory: 27320kb
input:
3 4 546909
output:
341817
result:
ok single line: '341817'
Test #50:
score: 0
Accepted
time: 17ms
memory: 27280kb
input:
2 2 932611
output:
932611
result:
ok single line: '932611'