记录编号 593071 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 篮球 最终得分 100
用户昵称 Gravatar1nclude 是否通过 通过
代码语言 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;
}