AtCoderABC135の問題Cについて

解決済

質問者：ktnabe
質問日時：2024/08/10 18:11
回答数：4件

お世話になっております。atCoderの勉強のためにABC135のC問題にトライしてみたのですが、ACにならず、17入力データ中4つしか通りません。プログラムのどこで間違えているのかわからないです。
https://atcoder.jp/contests/abc135/tasks/abc135_c

問題
N+1 個の街があり、
i 番目の街は A_i体のモンスターに襲われています。
N 人の勇者が居て、i 番目の勇者は i 番目または i+1 番目の街を襲っているモンスターを合計でB_i体まで倒すことができます。
N 人の勇者がうまく協力することで、合計して最大で何体のモンスターを倒せるでしょうか。

入力は以下のように与えられる。
N
A_1 A_2 ... A_{N+1}
B_1 B_2 ... B_N

例
2
3 5 2
4 5
＝＞9

作成したプログラムを以下に示します。
#include <iostream>
#include <vector>
using namespace std;

int main(){
int n, b_i, b_iadd1=0;
int B_i; // i番目の勇者が倒せる怪物の数
int sum = 0;
cin >> n;
vector<int> a(n+2); // 怪物の数
for(int i=1; i<=n+1; i++) cin >> a[i];
for(int i=1; i<=n; i++) {
cin >> B_i;
b_i = min(a[i] - b_iadd1, B_i);
b_iadd1 = min(a[i+1], B_i - b_i);
sum += b_i + b_iadd1;
}
cout << sum;
return 0;
}

改善箇所を教えていただきたいです。よろしくお願いします

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

ベストアンサー優先
最新から表示
回答順に表示

No.1ベストアンサー

回答者： tatsumaru77
回答日時：2024/08/11 00:10

int sum = 0;

を
long long int sum = 0;
に変えてください。
sumの最大値は、10の9乗 × １０の５乗　＝１０の１４乗
になるので、int型では格納できません。
long long int型であれば、十分格納可能です。

- 0
- 件

通報する

この回答へのお礼

ご指摘いただいたように、sumでオーバーフローが生じていたようでした。型を変更することで、無事にacを取れました！今後も一部の入力に対してうまくいかない場合は型の確認をするように注意します！助かりました！！
ベストアンサーが選択可能になったら、1番さんを選ばせていただきます。
ありがとうございました

通報する

お礼日時：2024/08/11 06:43