QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102660 | #5259. Skills in Pills | zswzswzsw# | TL | 0ms | 0kb | C++14 | 1.7kb | 2023-05-03 15:39:11 | 2023-05-03 15:39:13 |
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)
{
if(n<pos0)ans=n/a+n/b;
for(int i=1;i<=n;i++)
{
dp1[i]=dp2[i]=n*3;
if(i<=pos0){
dp1[i]=pos0/a+pos0/b;
dp2[i]=pos0/a+pos0/b;
}
if(i-posa>0){
dp1[i]=min(dp1[i-posa]+posa/b+(posa+1)/a,dp1[i]);
dp2[i]=min(dp1[i-posa]+posa/b+(posa+1)/a,dp2[i]);
}
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;i--)
ans=min(ans,dp1[i]+(n-i)/b+(n-i+1)/a);
for(int i=n;i>=n-posb;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);
}
init();
solve2();
cout<<ans;
return 0;
}
/*
3 3 11
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 9 20