分析
坑点：
（你需要覆盖整个区间，而非只覆盖整数点，例如 \(n=3\)，\([0,1],[2,3]\) 是不够的。）
翻译没把这个写上去，搞得我思考了很久样例。看到这个之后，题目可以转化为每个灯可以覆盖 \([x,x+l)\)，你需要覆盖区间 \([0,n)\) 中的整数点。
如果没有障碍物，我们直接枚举每个灯放哪，复杂度 \(O(\displaystyle\sum_{i=1}^k\frac{n}{i})=O(n \log n)\)。现在有障碍，考虑开一个数组 \(pre_i\) 表示下标小于 \(i\) 下标最大的非障碍物坐标。每次如果是障碍就跳到 \(pre_i\)，最多跳 \(m\) 次，复杂度可以保证，不过常数有点大，要用快读。
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000010],n,m,k,s[1000010],pre[1000010],mp[1000010];
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x / 10);
putchar(x%10+'0');
return;
}
int add(int l)
{
int ret=0;
for(int i=0;i<n;i+=l)
{
ret++;
if(mp[i]) i=pre[i];
}
return ret;
}
signed main()
{
n=read();m=read();k=read();
if(n==m)
{
puts("-1");
return 0;
}
s[0]=-1e18;
for(int i=1;i<=m;i++)
{
s[i]=read();
mp[s[i]]=1;
if(!s[i])
{
puts("-1");
return 0;
}
}
for(int i=1;i<=k;i++) a[i]=read();
for(int i=1;i<=n;i++) pre[i]=(mp[i-1]?pre[i-1]:i-1);
int tp=1,maxt=0;
for(int i=1;i<=m;i++)
{
if(s[i]!=s[i-1]+1) tp=1;
else tp++;
maxt=max(maxt,tp);
}
if(maxt+1>k)
{
puts("-1");
return 0;
}
int ans=1e18;
for(int i=maxt+1;i<=k;i++) ans=min(ans,add(i)*a[i]);
write(ans);
return 0;
}