ID490842577

只写了60分的暴力，斜率优化还没来得及写，题解等我把100分的写了再补吧。。

60分

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<vector>

#include<map>

using namespace std;

int n,m,a[100005],b[100005],f[100005];

long long cime;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

void fan2()

{

int x;

int ans[15][15];

memset(ans,0,sizeof(ans)); 

for (int i=1;i<=n;i++) f[i]=read();

for (int i=1;i<=10;i++)

{

for (int j=1;j<=n;j++) a[j]=i*f[j];

for (int j=1;j<=10;j++)

{

for (int k=1;k<=n;k++) b[k]=j*f[k];

long long ans1=0;

for (int k=1;k<n;k++) 

{

ans1+=a[k+1]-b[k];

if (ans1>0) ans[i][j]+=ans1,ans1=0;

}

}

}

x=read();

int y;

for (int i=2;i<=m;i++)

{

y=x;

cime+=y*f[1];

x=read();

cime+=ans[y][x];

}

for (int i=1;i<=n;i++) cime+=f[i]*x;

printf("%lld\n",cime);

return ;

}

int main()

{

freopen("yume.in","r",stdin);

freopen("yume.out","w",stdout);

cime=0;

n=read();m=read();

if (n>1000) 

{

fan2();

return 0;

}

for (int i=1;i<=n;i++) scanf("%d",&f[i]);

int x;

x=read();

for (int i=1;i<=n;i++) a[i]=x*f[i];

for (int i=2;i<=m;i++)

{

cime+=a[1];

x=read();

for (int j=1;j<=n;j++) b[j]=x*f[j];

long long ans1=0,ans2=0;

for (int j=1;j<n;j++) 

{

ans1+=a[j+1]-b[j];

if (ans1>0) ans2+=ans1,ans1=0;

}

//for (int j=1;j<n-1;j++) ans2+=max(b[j]-a[j+1],)

cime+=ans2;

for (int j=1;j<=n;j++) a[j]=b[j];

}

for (int i=1;i<=n;i++) cime+=a[i];

printf("%lld\n",cime);

return 0;

}