QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#102654 | #5259. Skills in Pills | zswzswzsw# | WA | 161ms | 14536kb | C++14 | 1.7kb | 2023-05-03 15:32:28 | 2023-05-03 15:32:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int res;
int n,a,b,lsta,lstb;
int ans=1e9+7;;
void solve(int opt,int t,int t1,int t2)
{
lsta=lstb=res=0;
lsta=t1;lstb=t2;
for(int i=1;i<=n;i++)
{
if(i-lsta>=a&&i-lstb>=b){
opt^=t;res+=2;
if(opt)lsta=i,lstb=i-1;
else lsta=i-1,lstb=i;
}
else if(i-lsta>=a){
++res;lsta=i;
}
else if(i-lstb>=b){
++res;lstb=i;
}
}ans=min(res,ans);
}
const int N=2010000;
int dp1[N],dp2[N];
int posa,posb,pos0;//a<b;a>b;
void init(void)
{
lsta=-1;lstb=0;
for(int i=1;i;i++){
if(i-lsta==a&&i-lstb==b){posa=i;break;}
if(i-lsta==a)lsta=i;
if(i-lstb==b)lstb=i;
}
lsta=0;lstb=-1;
for(int i=1;i;i++){
if(i-lsta==a&&i-lstb==b){posb=i;break;}
if(i-lsta==a)lsta=i;
if(i-lstb==b)lstb=i;
}
lsta=0;lstb=0;
for(int i=1;i;i++){
if(i-lsta==a&&i-lstb==b){pos0=i;break;}
if(i-lsta==a)lsta=i;
if(i-lstb==b)lstb=i;
}return;
}
void solve2(void)
{
for(int i=1;i<=n;i++)
{
dp1[i]=dp2[i]=n*3;
if(i<=pos0){
dp1[i]=pos0/a+pos0/b+1;
dp2[i]=pos0/a+pos0/b+1;
}
if(i-posa>0){
dp1[i]=dp1[i-posa]+posa/b+(posa+1)/a;
dp2[i]=dp1[i-posa]+posa/b+(posa+1)/a;
}
if(i-posb>0){
dp1[i]=min(dp1[i],dp2[i-posb]+posb/a+(posb+1)/b);
dp2[i]=min(dp2[i],dp2[i-posb]+posb/a+(posb+1)/b);
}
}
for(int i=n;i>=n-posa+1;i--)
ans=min(ans,dp1[i]+(n-i)/b+(n-i+1)/a);
for(int i=n;i>=n-posb+1;i--)
ans=min(ans,dp2[i]+(n-i)/a+(n-i+1)/b);
return;
}
int main()
{
cin>>a>>b>>n;
for(int i=-5;i<=0;i++)
for(int j=-5;j<=0;j++){
solve(1,0,i,j);
solve(1,1,i,j);
solve(0,0,i,j);
solve(0,1,i,j);
}
solve2();
cout<<ans;
return 0;
}
/*
3 3 11
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5380kb
input:
3 9 20
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5312kb
input:
8 2 12
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5380kb
input:
2 5 15
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5304kb
input:
10 8 13
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5424kb
input:
6 6 19
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5372kb
input:
2 3 5
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5504kb
input:
4 2 8
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 2ms
memory: 5376kb
input:
5 5 5
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 5488kb
input:
3 8 11
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5560kb
input:
5 8 16
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 2ms
memory: 5380kb
input:
9 7 279
output:
70
result:
ok single line: '70'
Test #12:
score: 0
Accepted
time: 2ms
memory: 5384kb
input:
8 3 56
output:
25
result:
ok single line: '25'
Test #13:
score: 0
Accepted
time: 2ms
memory: 5324kb
input:
5 9 46
output:
14
result:
ok single line: '14'
Test #14:
score: 0
Accepted
time: 2ms
memory: 5536kb
input:
8 4 251
output:
93
result:
ok single line: '93'
Test #15:
score: 0
Accepted
time: 2ms
memory: 5484kb
input:
8 7 41
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 2ms
memory: 5552kb
input:
60 17 360
output:
27
result:
ok single line: '27'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5560kb
input:
16 55 388
output:
31
result:
ok single line: '31'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5488kb
input:
25 38 292
output:
18
result:
ok single line: '18'
Test #19:
score: 0
Accepted
time: 2ms
memory: 5384kb
input:
22 59 177
output:
11
result:
ok single line: '11'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5320kb
input:
4 3 82
output:
50
result:
ok single line: '50'
Test #21:
score: 0
Accepted
time: 78ms
memory: 10952kb
input:
77 18 511543
output:
35070
result:
ok single line: '35070'
Test #22:
score: 0
Accepted
time: 126ms
memory: 13756kb
input:
37 32 987861
output:
57612
result:
ok single line: '57612'
Test #23:
score: 0
Accepted
time: 44ms
memory: 9492kb
input:
29 8 300899
output:
48059
result:
ok single line: '48059'
Test #24:
score: 0
Accepted
time: 73ms
memory: 9848kb
input:
73 83 533839
output:
13745
result:
ok single line: '13745'
Test #25:
score: 0
Accepted
time: 25ms
memory: 9736kb
input:
12 23 181193
output:
23008
result:
ok single line: '23008'
Test #26:
score: 0
Accepted
time: 147ms
memory: 14536kb
input:
2 2 864514
output:
864514
result:
ok single line: '864514'
Test #27:
score: 0
Accepted
time: 25ms
memory: 9652kb
input:
27 7 165249
output:
29765
result:
ok single line: '29765'
Test #28:
score: 0
Accepted
time: 114ms
memory: 12128kb
input:
15 2 751665
output:
429522
result:
ok single line: '429522'
Test #29:
score: 0
Accepted
time: 125ms
memory: 13596kb
input:
2 16 818146
output:
460207
result:
ok single line: '460207'
Test #30:
score: 0
Accepted
time: 84ms
memory: 11688kb
input:
43 88 631366
output:
21860
result:
ok single line: '21860'
Test #31:
score: 0
Accepted
time: 0ms
memory: 5320kb
input:
215 1222 3597
output:
18
result:
ok single line: '18'
Test #32:
score: 0
Accepted
time: 77ms
memory: 11632kb
input:
9619 3375 604892
output:
241
result:
ok single line: '241'
Test #33:
score: 0
Accepted
time: 39ms
memory: 6596kb
input:
861 1924 311511
output:
522
result:
ok single line: '522'
Test #34:
score: 0
Accepted
time: 115ms
memory: 14440kb
input:
9249 3782 866972
output:
322
result:
ok single line: '322'
Test #35:
score: 0
Accepted
time: 29ms
memory: 6172kb
input:
7055 8386 206874
output:
53
result:
ok single line: '53'
Test #36:
score: 0
Accepted
time: 18ms
memory: 5808kb
input:
6273 7732 122377
output:
34
result:
ok single line: '34'
Test #37:
score: 0
Accepted
time: 14ms
memory: 5904kb
input:
8057 7746 89137
output:
22
result:
ok single line: '22'
Test #38:
score: 0
Accepted
time: 12ms
memory: 5680kb
input:
9215 8952 74618
output:
16
result:
ok single line: '16'
Test #39:
score: 0
Accepted
time: 20ms
memory: 7648kb
input:
7246 3709 129579
output:
51
result:
ok single line: '51'
Test #40:
score: 0
Accepted
time: 103ms
memory: 13232kb
input:
4052 6785 831888
output:
327
result:
ok single line: '327'
Test #41:
score: 0
Accepted
time: 17ms
memory: 7944kb
input:
9 2 91067
output:
56916
result:
ok single line: '56916'
Test #42:
score: 0
Accepted
time: 130ms
memory: 13836kb
input:
10 3 913595
output:
406041
result:
ok single line: '406041'
Test #43:
score: 0
Accepted
time: 30ms
memory: 9632kb
input:
2 2 152575
output:
152575
result:
ok single line: '152575'
Test #44:
score: 0
Accepted
time: 161ms
memory: 12932kb
input:
2 2 927771
output:
927771
result:
ok single line: '927771'
Test #45:
score: 0
Accepted
time: 91ms
memory: 10848kb
input:
6 7 637014
output:
200204
result:
ok single line: '200204'
Test #46:
score: 0
Accepted
time: 121ms
memory: 13728kb
input:
5 3 721417
output:
400786
result:
ok single line: '400786'
Test #47:
score: 0
Accepted
time: 25ms
memory: 6044kb
input:
5 9 183079
output:
57538
result:
ok single line: '57538'
Test #48:
score: -100
Wrong Answer
time: 88ms
memory: 13168kb
input:
9 2 579290
output:
362056
result:
wrong answer 1st lines differ - expected: '362055', found: '362056'