记录编号 |
593071 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
篮球 |
最终得分 |
100 |
用户昵称 |
1nclude |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.721 s |
提交时间 |
2024-08-15 20:33:13 |
内存使用 |
4.42 MiB |
显示代码纯文本
#include<bits/stdc++.h>
#define get(x) if(sizeof(x)==8){scanf("%lld",&x);}else{scanf("%d",&x);}
#define put(x) if(sizeof(x)==8){printf("%lld",x);}else{printf("%d",x);}
#pragma GCC optimize(2)
#pragma G++ optimize(2)
using namespace std;
int l[2005]={},r[2005]={};
long long int a[1005]={},b[2005]={},f[2005][3][3];
int n,m;
unordered_map<long long int,bool> mp;
void loadgcd()
{
for(int i=1;i<=m;i++)
{
for(int j=i+1;j<=m;j++)
{
mp[__gcd(a[i],a[j])]=1;
}
}
}
long long int dfs(int x,int lwalk,int rwalk)
{
if(f[x][lwalk][rwalk]!=0x7f7f7f7f7f7f7f7f) return f[x][lwalk][rwalk];
if(x==0) return f[x][lwalk][rwalk]=0;
if(lwalk==0&&rwalk==0&&mp[b[x]]) return f[x][lwalk][rwalk]=min(min(min(min(dfs(x-1,0,0),dfs(x-1,1,0)),dfs(x-1,2,0)),dfs(x-1,0,1)),dfs(x-1,0,2));
else if(lwalk==0&&rwalk==1) return f[x][lwalk][rwalk]=min(min(dfs(x-1,1,0)+r[x],dfs(x-1,2,0)+r[x]),dfs(x-1,0,0)+r[x]);
else if(lwalk==0&&rwalk==2) return f[x][lwalk][rwalk]=dfs(x-1,0,1)+r[x];
else if(lwalk==1&&rwalk==0) return f[x][lwalk][rwalk]=min(min(dfs(x-1,0,1)+l[x],dfs(x-1,0,2)+l[x]),dfs(x-1,0,0)+l[x]);
else if(lwalk==2&&rwalk==0) return f[x][lwalk][rwalk]=dfs(x-1,1,0)+l[x];
else return f[x][lwalk][rwalk]=0x7f7f7f7f7f7f7f7f;
}
int main()
{
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
get(n);
get(m);
for(int i=1;i<=m;i++) get(a[i]);
for(int i=1;i<=n;i++) get(b[i]);
for(int i=1;i<=n;i++) get(l[i]);
for(int i=1;i<=n;i++) get(r[i]);
loadgcd();
memset(f,0x7f,sizeof(f));
if(mp[b[n]])
{
put(min({dfs(n,0,0),dfs(n,1,0),dfs(n,2,0),dfs(n,0,1),dfs(n,0,2)}));
}else{
put(min({dfs(n,1,0),dfs(n,2,0),dfs(n,0,1),dfs(n,0,2)}));
}
return 0;
}