long long と　int （競技プログラミング）

以下のリンクのプログラミング問題について
AtCoder C問題

競技プログラミングで以下のように cnt を定義したのですが、これでは全てのテストコードにおいて WA でした。

C++
1int cnt = 0;

以下に書き換えたら AC できたのですが、調べたらメモリの関係のようでしたがはっきり分かりませんでした。
この問題に関して具体的に教えていただきたいです。

また、forn文のintはllに変えなくていいのはなぜでしょうか？

C++
1ll cnt = 0;

問題の制約
入力は全て整数である。
・　1≤N≤10^5
・　1≤A_i≤10^9
・　1≤B_i≤10^9

C++
1#include<bits/stdc++.h>
2#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
3using namespace std;
4typedef long long ll;
5
6
7int main() {
8
9    int N;
10    cin >> N;
11    vector<int> A(N+1), B(N);
12    forn(i, N + 1) cin >> A[i];
13    forn(i, N) cin >> B[i];
14    ll cnt = 0;
15
16    forn(i, N) {
17        if (B[i] <= A[i]) {
18            cnt += B[i];
19        } else if (B[i] <= A[i] + A[i+1]) {
20            cnt += B[i];
21            A[i+1] = A[i] + A[i+1] - B[i];
22        } else {
23            cnt += A[i] + A[i+1];
24            A[i+1] = 0;
25        }
26    }
27    cout << cnt << endl;
28}

行動規範の内容に同意します

回答2件

ベストアンサー

cntには最大10^9を最大10^5回足し算した結果を格納する必要があります。
10^9*10^5=10^14を16進数にすると5af3107a4000となり6Byteすなわち48bit必要です。
intでは収まりません。よって、48bitの値を格納可能であるlong longを使用します。

投稿2019/10/22 08:51