Atcoder 部分和問題

Question

Atcoderの部分和問題でWAが出てしまいます。
Bit全探索をしようと思っているのですが、入力例２の出力が正しく出てきません。
どこが間違っているのでしょうか。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

string S;

ll solve(){
    ll sum=0;
    for(int bit=0; bit < ( 1<<S.size()-1 ); bit++){
        int cnt=1;
        sum += S[0] - '0';
        for(int i=0; i<S.size()-1; i++){
            if(bit & (1<<i)){
                cnt = 1;
                sum += S[i+1] - '0';
            }
            else{
                cnt *= 10;
                sum += cnt * ( S[i+1] - '0' );
            }
        }
    }
    return sum;
}

int main() {
    cin >> S;
    reverse(S.begin(), S.end());
    cout << solve() << endl;
}

Answer 1

cntがintなので掛け算でオーバーフローしています。
ll cnt=1;に変えると、サンプル2が合いました。

Comments

[hakubo2]

ありがとうございます。
cntは最悪10^10されますね。
感謝いたします。