比赛 |
20131207 |
评测结果 |
AAAAAATATTTTW |
题目名称 |
不设找零 |
最终得分 |
53 |
用户昵称 |
digital-T |
运行时间 |
5.253 s |
代码语言 |
C++ |
内存使用 |
0.67 MiB |
提交时间 |
2013-12-07 16:58:51 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int N,K,coin[17],sum[100001],Ans=-1;
int plan[17];
bool boo[17];
int do_do()
{
/*for(int i=1;i<=K;i++)
printf("%d ",coin[plan[i]]);
printf("\n");*/
int pre=0,temp,p1,p2,mid;
for(int i=1;i<=K;i++)
{
if(pre==N)
{
int ans=0;
for(int j=i;j<=K;j++)
ans+=coin[plan[j]];
//printf("\n");
return ans;
}
p1=pre;
p2=N;
while(p2-p1>1)
{
if(sum[mid=(p2+p1)/2]-sum[pre]==coin[plan[i]])
p1=p2=mid;
else
{
if(sum[mid=(p2+p1)/2]-sum[pre]>coin[plan[i]])
p2=mid;
else
p1=mid;
}
}
mid=(p1+p2)/2;
while(mid<N&&sum[mid+1]-sum[pre]<=coin[plan[i]])
mid++;
//printf("%d %d %d\n",mid,pre,sum[mid]-sum[pre]);
pre=mid;
//printf("%d ",pre);
}
//printf("\n");
if(pre==K)
return 0;
return -1;
}
void dfs(int step,int x)
{
plan[step]=x;
boo[x]=1;
if(step==K)
{
Ans=max(Ans,do_do());
//printf("%d\n",Ans);
goto NEXT;
}
for(int i=1;i<=K;i++)
if(!boo[i])
dfs(step+1,i);
NEXT:;
boo[x]=0;
plan[step]=0;
}
int main()
{
freopen("nochange.in","r",stdin);
freopen("nochange.out","w",stdout);
scanf("%d%d",&K,&N);
for(int i=1;i<=K;i++)
scanf("%d",&coin[i]);
int temp;
sum[0]=0;
for(int i=1;i<=N;i++)
{
scanf("%d",&temp);
sum[i]=sum[i-1]+temp;
}
dfs(0,0);
printf("%d",Ans);
return 0;
}