Algorithm: maximum flow, min-cut

The network will consist of n + 2 vertices,

the source point located at the node with the number 0 and the sink at the node with the number n + 1.

For each node i such that 1 ≤ i ≤ n add the arc (0, i) with a capacity pi

and arc (i, n + 1) with capacity si.

Also, for each pair of nodes i and j such that 1 ≤ i < j ≤ n, add the arc (i, j) with capacity c,

so that the answer is just the maximum flow of the network.

but there are n^2/2 edges, so it's not available to get the answer of max-flow, you need to use dp to work out the min-cut, for the max-flow is equal to min-cut.

define i as the position and j, j is on the left of position i, there are j cities connecting to the source.

then

setmin(f[i][j+1],f[i-1][j]+s[i])

setmin(f[i][j],f[i-1][j]+p[i]+j*c)

here is the code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <string>
#include <cstdlib>
#define longlongtype
using namespace std;
typedef long long LL;
#define ref(i,x,y)for(int i=x;i<=y;i++)
#define def(i,x,y)for(int i=x;i>=y;i--)
#ifdef longlongtype
	typedef long long LL;
	#define T LL
	const T oo=1e16;
#endif
#ifdef inttype
	#define T int
	const T oo=2e9;
#endif
T max(T a,T b){return a>b?a:b;};
T min(T a,T b){return a<b?a:b;};
T gcd(T a,T b){return b?gcd(b,a%b):a;};
T read(){char c=getchar();T d=0,f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());return d*f;}
T n,c,ans,a[10001],b[10001],f[10001];
int main()
{
	n=read(),c=read();
	ref(i,1,n)a[i]=read();
	ref(i,1,n)b[i]=read();
	ref(i,1,n)f[i]=oo;
	ref(i,1,n)def(j,i-1,0)
	{
		f[j+1]=min(f[j+1],f[j]+b[i]);
		f[j]=f[j]+a[i]+j*c;
	}
	ans=oo;
	ref(i,0,n)ans=min(ans,f[i]);
	printf("%I64d\n",ans);
}