AtCoder Beginner Contest087_C Candies

Question

#AtCoder Beginner Contest087_C Candies

こちらの問題について質問があります。
##問題
087_C

2×Nのマス目があります。上から i行目、左から j列目 (1≤i≤2,1≤j≤N) のマスをマス (i,j)と表すことにします。

あなたははじめ、左上のマス (1,1)にいます。 あなたは、右方向または下方向への移動を繰り返し、右下のマス (2,N)に移動しようとしています。
マス (i,j)には Ai,j個のアメが置かれています。 あなたは移動中に通ったマスに置いてあるアメをすべて回収します。
左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
移動方法をうまく選んだとき、最大で何個のアメを回収できるでしょうか。

###入力例

5
3 2 2 4 1
1 2 2 2 1

#出力例

14

##質問

dpや2重ループでの解法が考えられますが、今回はupper_total, lower_sumをそれまでの上部のマスの和を用いて実装をしています。
sampleのテストケースは通るのですがACを出すことができません。

##私の実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    int A[2][N];

    //入力
    for(int i=0; i<2; i++) for(int j=0; j<N; j++) cin >> A[i][j];
    //上部の和(A[0][0]は除く)と, 下部の輪(A[0][N-1]は除く)を求める
    ll upper_total = 0;
    ll lower_total = 0;

    for(int i=1; i<N; i++) upper_total += A[0][i];
    for(int i=0; i<N-1; i++) lower_total += A[1][i];

    ll ans = A[0][0] + A[1][N-1];
    for(int j=1; j<N; j++) {
        if(upper_total > lower_total) {
            ans += A[0][j];
            upper_total -= A[0][j];
            lower_total -= A[1][j-1];
        }

        //下部の和の方が大きい時にはlower_totalを加えてループを終わらせる
        else if(lower_total >= upper_total) {
            ans += lower_total;
            break;
        }
    }

    cout << ans << endl;
}

サンプルケースはあっているので大きくは間違っていないとは思うのですが、
どこに問題があるのかがわかりません。

何かアドバイスをいただけると幸いです。よろしくお願いいたします。

Answer 1

3
7 5 3
3 5 7
という入力の場合、24 になってほしいのに、そのコードでは 22 になります。
その原因を調べてみてください。

私なら次のようなコードを書きます。

#include <iostream>
using namespace std;

int main()
{
	int n, a[2][100];
	cin >> n;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	int sum = a[0][0];
	for (int j = 0; j < n; j++)
		sum += a[1][j];
    int max = sum;
	for (int i = 1; i < n; i++) {
		sum += a[0][i] - a[1][i-1];
		if (sum > max) max = sum;
	}
	cout << max << endl;
}