QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #507213 | #5259. Skills in Pills | ucup-team1525# | WA | 2ms | 23492kb | C++20 | 2.2kb | 2024-08-06 13:45:48 | 2024-08-06 13:45:49 |
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;
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,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: 23416kb
input:
3 9 20
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 23288kb
input:
8 2 12
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 0ms
memory: 22040kb
input:
2 5 15
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 0ms
memory: 21840kb
input:
10 8 13
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 23492kb
input:
6 6 19
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 0ms
memory: 22280kb
input:
2 3 5
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 22368kb
input:
4 2 8
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 0ms
memory: 22716kb
input:
5 5 5
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 23400kb
input:
3 8 11
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 2ms
memory: 22248kb
input:
5 8 16
output:
5
result:
ok single line: '5'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 21860kb
input:
9 7 279
output:
72
result:
wrong answer 1st lines differ - expected: '70', found: '72'