QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#102660#5259. Skills in Pillszswzswzsw#TL 0ms0kbC++141.7kb2023-05-03 15:39:112023-05-03 15:39:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 15:39:13]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-05-03 15:39:11]
  • 提交

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
*/

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

3 9 20

output:


result: