#include #include using namespace std; // 575 const int64_t INF2 = 1125899906842623; // 2^50-1、使わない辺とかに用いる int main() { int64_t N, M, A, B; cin >> N >> M >> A >> B; int64_t dp[3] = {max(max(M * A, (M - 1) * A + B), B), -INF2, -INF2}; while (--N) { cin >> A >> B; dp[2] = max(max(dp[0], dp[1]), dp[2]); dp[1] = max(dp[0], dp[1]) + max(A, B); dp[0] = dp[0] + max(max(M * A, (M - 1) * A + B), B); } cout << max(max(dp[0], dp[1]), dp[2]) << endl; return 0; } /* 31536000のコメント解説欄 ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー まず、各鶏についてとれる行動を列挙してみる 1. M日間卵を産ませる 2. M-1日間卵を産ませ、M日目に鶏肉にする 3. 1日目に卵を産ませる 4. 1日目に鶏肉にする 5. 選ばない これ以外は最適ではないため、常にこの行動になる よって、各鶏についてはこう考えることができる 1. 毎日選ばれる (max(MA, (M-1)A+B, B)) 2. 1日目だけ選ばれる (max(A, B)) 3. 選ばれない (0) ということで、これを状態に動的計画法を考えることができる dp1[i]はiが毎日選ばれる鶏の時の美味しさの最大値、 dp2[i]はiが1日目だけ選ばれる鶏の時の美味しさの最大値、 dp3[i]はiが選ばれない鶏の時の美味しさの最大値 dp1[i]=dp1[i-1]+max(MA, (M-1)A+B, B) dp2[i]=max(dp1[i-1], dp2[i-1])+max(A, B) dp3[i]=max(dp1[i-1], dp2[i-1], dp3[i-1]) よし、遷移が組めました 計算量はO(N)です */