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"; }