この問題は、次の \(2\) つの方針で解くことができます。

• DP を高速化する方法
• 答えの性質について数学的な考察を行い場合分けをして解く方法

それぞれについて解説を行います。

---

1. DP を高速化する方法

この問題は、制約が \(N\le10 ^ 5\) などであれば、次のような DP を行うことで十分高速に解くことができます。

\(\operatorname{dp} _ A[i]\coloneqq i\) 日目まで水やりを行い、最後に行った水やりが方法 A であるときの \(i\) 日目までの成長量の合計としてありえる最大値、\(\operatorname{dp} _ B[i]\coloneqq i\) 日目まで水やりを行い、最後に行った水やりが方法 B であるときの \(i\) 日目までの成長量の合計としてありえる最大値とする。\(\operatorname{dp} _ A[0]=\operatorname{dp} _ B[0]=0\) として、\(i=1,2,\ldots,N\) に対して以下のように DP を行う。\[\operatorname{dp} _ A[i]=\max\lbrace\operatorname{dp} _ A[i-1]+\lfloor A/2\rfloor,\operatorname{dp} _ B[i-1]+A\rbrace\]\[\operatorname{dp} _ B[i]=\max\lbrace\operatorname{dp} _ A[i-1]+\lfloor B/2\rfloor,\operatorname{dp} _ B[i-1]+B\rbrace\] \(\operatorname{dp} _ A[N],\operatorname{dp} _ B[N]\) のうち小さくない方が求める答えである。

この DP は \(\Theta(N)\) 時間かかってしまうためこのままではこの問題を解くことはできません。 しかし、この DP の遷移は \(i\) によらないため、次のような値を考えることができます。

直前の水やりの方法が A であるところから \(k\) 日間水やりを行って最後に方法 A の水やりを行うときの \(k\) 日間の成長量の合計としてありえる最大値 \(f _ {AA}(i)\) および同様に \(f _ {AB}(i),f _ {BA}(i),f _ {BB}(i)\)

自然数 \(i,j\) に対して \(f _ {AA}(i),f _ {AB}(i),f _ {BA}(i),f _ {BB}(i)\) と \(f _ {AA}(j),f _ {AB}(j),f _ {BA}(j),f _ {BB}(j)\) の値がわかっているとき、定数時間で \(f _ {AA}(i+j),f _ {AB}(i+j),f _ {BA}(i+j),f _ {BB}(i+j)\) の値を求めることができます。 よって、これを利用してダブリングのようにして答えを \(O(\log N)\) 時間で求めることができます。 この操作は max-plus 半環上の行列累乗だと考えることもできます。

実装例は以下のようになります。

#include <iostream>
#include <array>
#include <algorithm>
using namespace std;

int main(){
    long N, a, b;
    cin >> N >> a >> b;

    // f(i) と f(j) から f(i + j) を求める
    const auto prod{[](const array<long, 4>& lhs, const array<long, 4>& rhs){
        return array<long, 4>{{
            max(lhs[0] + rhs[0], lhs[1] + rhs[2]),
            max(lhs[0] + rhs[1], lhs[1] + rhs[3]),
            max(lhs[2] + rhs[0], lhs[3] + rhs[2]),
            max(lhs[2] + rhs[1], lhs[3] + rhs[3])
        }};
    }};

    // f(1) は a/2, b/2, a, b
    array<long, 4> ans{{a / 2, b / 2, a, b}}, coef{ans};
    --N;

    // ダブリング（繰り返し二乗法）
    while (N) {
        if (N & 1)
            ans = prod(ans, coef);
        coef = prod(coef, coef);
        N /= 2;
    }

    // f(N) の最大値が答え
    cout << ranges::max(ans) << endl;
    return 0;
}

N, a, b = map(int, input().split())

# f(i) と f(j) から f(i + j) を求める
def prod(lhs, rhs):
    return (max(lhs[0] + rhs[0], lhs[1] + rhs[2]), max(lhs[0] + rhs[1], lhs[1] + rhs[3]), max(lhs[2] + rhs[0], lhs[3] + rhs[2]), max(lhs[2] + rhs[1], lhs[3] + rhs[3]))

# f(1) は a//2, b//2, a, b
ans = (a // 2, b // 2, a, b)
coef = (a // 2, b // 2, a, b)
N -= 1

# ダブリング（繰り返し二乗法）
while N > 0:
    if N % 2 == 1:
        ans = prod(ans, coef)
    coef = prod(coef, coef)
    N //= 2

# f(N) の最大値が答え
print(max(ans))

---

2. 答えの性質について数学的な考察を行い場合分けをして解く方法

まず、\(a\le b\) のとき、毎日方法 B で水やりをするのが最適です。

そうでないとき、\(b\lt a\) が成り立ちます。 \(b\lt a\) より、最終日は方法 A で水やりをするほうがよいので、少なくとも \(1\) 日は方法 A で水やりを行います。 \(N\) 日のうち方法 A で水やりをする日数が \(K\) 日であるときの成長量の合計の最大値を \(f(K)\) と表すことにします。

最終日が方法 A でないとき、最初の方法 A の日と入れ替えることで成長量の合計が増加するため、最終日の水やりは方法 A であるとしてよいです。 それ以外の、方法 A で水やりをする \(K-1\) 日のうち、直後の日の水やりの方法が A である日数を \(c _ A\) とします。 すると、成長量の合計は \(Ka+(N-K)b-c _ A(a-\lfloor a/2\rfloor)-(K-1-c _ A)(b-\lfloor b/2\rfloor)\) となります。 整数 \(x\) に対して、\(x-\left\lfloor\dfrac x2\right\rfloor=\left\lfloor\dfrac{x+1}2\right\rfloor\) が成り立つことが知られている（\(x\) の偶奇で場合分けをすることで示せます）ので、これは \(Ka+(N-K)b-c _ A\lfloor(a+1)/2\rfloor-(K-1-c _ A)\lfloor(b+1)/2\rfloor\) となります。

\(b\lt a\) なので、\(c _ A\) を減らせば成長量の合計は増えていくため、\(c _ A\) を最小にすることで成長量の合計を最大にすることができます。 \(K-1\le N-K\) ならば \(c _ A=0\) とできます。 そうでなければ \(c _ A=2K-N-1\) です。

これを整理して、\[f(K)=\begin{cases}Nb+\left\lfloor\dfrac{b+1}2\right\rfloor+K\left(a-b-\left\lfloor\dfrac{b+1}2\right\rfloor\right)\quad&(K-1\le N-K)\\ N\left\lfloor\dfrac b2\right\rfloor+(N+1)\left\lfloor\dfrac{a+1}2\right\rfloor+K\left(a-2\left\lfloor\dfrac{a+1}2\right\rfloor\right)&(\text{otherwise})\end{cases}\] となります。

式の形を見ると、これはそれぞれの区間で一次関数になっており、特にそれぞれの区間で単調です。 よって、それぞれの区間の端点となる \(K=1,\left\lfloor\dfrac{N+1}2\right\rfloor,\left\lceil\dfrac{N+1}2\right\rceil,N\) それぞれにおける \(f(K)\) の値のうち最大のものが答えとなることがわかります。 傾きや端点での値をさらに評価することで \(N,a,b\) の値から最大値をとる \(K\) の値を閉じた式で得ることができます（特に \(K=N\) が最適になることはないこともわかります）が、この 4 つを判定すれば十分です。

実装例は以下のようになります。 C++ の実装例は端点の値を評価して答えを閉じた式にしたものとなっており、Python の実装例では答えの候補となる \(O(1)\) 個の値の最大値を求めることで答えを求めています。

#include <iostream>
using namespace std;

int main(){
    long N, a, b;
    cin >> N >> a >> b;
    if (a <= b) {
        cout << N * b << endl; // K = 0, BBBB..BB
    } else if (a <= (3 * b + 1) / 2) {
        cout << (N - 1) * b + a << endl; // K = 1, BBBB..BA
    } else if (N % 2 == 1) {
        cout << (N + 1) / 2 * a + N / 2 * (b / 2) << endl; // K = (N+1)/2, ABAB..BA
    } else if (a / 2 <= b) {
        cout << (N / 2) * a + (N / 2 - 1) * (b / 2) + b << endl; // K = N/2, BABA..BA
    } else {
        cout << (N / 2) * a + (N / 2 - 1) * (b / 2) + a / 2 << endl; // K = N/2+1, AABA..AA
    }
    return 0;
}

N, a, b = map(int, input().split())

print(max((N - 1) * b + max(a, b), (N + 1) // 2 * a + N // 2 * (b // 2), N // 2 * a + (N // 2 - 1) * (b // 2) + max(b, a // 2)))