Educational DP Contest M - Candies - procon-kirokuyou

Educational DP Contest M - Candies

$ dp[i番目の人までで][j個持っている] というDPで解く

普通に遷移をするとk通り遷移があるため、全体で$ O(NK^2)になる

遷移元は連続しているため$ dp[i] 毎に累積和を取ると遷移にかかる時間が$ O(1)になり全体で$ O(NK)

飴は余っては駄目なので最後の一人でk個飴を使い切っている場合の数のみが答え

問題: https://atcoder.jp/contests/dp/tasks/dp_m

提出: https://atcoder.jp/contests/dp/submissions/6905386