ARC067

C
はい。
D
min(B, A * dist)で移動すればいいです。
E
普通にdpするとO(N^3)と見せかけてO(N^2logN)なので間に合います。速く書けてよかった。

void solve() {
	cin >> N >> A >> B >> C >> D;
	C_init(N + 50);

	dp[A][N] = 1;

	for(int i = A; i <= B; i++) {
		rep(n, 0, N + 1) {
			if(!dp[i][n]) continue;
			for(int j = C; j <= D; j++) {
				if(n - i * j >= 0) {
					ADD(dp[i + 1][n - i * j], 
							dp[i][n] * C_(n, i * j) % mod * fac[i * j] % mod * invf(mod_pow(fac[i], j)) % mod * fiv[j] % mod);
				}
				else break;
			}
			ADD(dp[i + 1][n], dp[i][n]);
		}
	}
	cout << dp[B + 1][0] << "\n";
}

F
JOI Cakeみたいな?最大値に注目して区間を分けるやつです。
スライド最小値に思考が行ってしまい良くなかった。
Mo?とも思ったんですが、MoはQが小さいのが本質で、今回はO(N^2)通り試すので使えません。

int N, M;
segtree seg;
ll A[MAX_N];
ll B[5010][210];
ll S[5010][5010];

void addblock(int x1, int x2, int y1, int y2, ll x) {
	S[x1][x2] += x;
	S[x1][y2] -= x;
	S[y1][x2] -= x;
	S[y1][y2] += x;
}


void dfs(int a, int b, int mi, int mj) {
	if(a == b) return;
	pl p = seg.get(a, b).v;
	ll v = p.fst; int t = p.sec;
	addblock(mi, t, t + 1, mj, v);
	dfs(a, t, mi, t);
	dfs(t + 1, b, t + 1, mj);
}

void solve() {
	cin >> N >> M;
	rep(i, 1, N) cin >> A[i];
	rep(i, 1, N + 1) A[i + 1] += A[i];
	rep(i, 0, N) 
		rep(j, 0, M) cin >> B[i][j];

	seg.init(N);
	rep(i, 0, M) {
		rep(j, 0, N) seg.update(j, T(pl(B[j][i], j)));
		dfs(0, N, 0, N);
	}
	rep(i, 0, N + 1) {
		rep(j, 0, N) {
			S[i][j + 1] += S[i][j];
		}
	}
	rep(j, 0, N + 1) {
		rep(i, 0, N) {
			S[i + 1][j] += S[i][j];
		}
	}
	ll ans = 0;
	rep(i, 0, N) {
		rep(j, i, N + 1) {
			MAX(ans, S[i][j] - (A[j] - A[i]));
		}
	}
	cout << ans << "\n";
}