1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string a, b, c;
    cin >> a >> b >> c;
    int n = (int)a.size();

    // For each position k (0-indexed, rightmost = n-1):
    //   r[k] = required carry_in for the digit to be valid (-1 if impossible)
    //   q[k] = carry_out when valid  =  (a[k]+b[k]+r[k]) / 10
    //
    // Each digit accepts AT MOST ONE carry value (0 or 1), because
    // (a[k]+b[k])%10 and (a[k]+b[k]+1)%10 always differ.
    vector<int> r(n, -1), q(n, -1);
    for (int k = 0; k < n; k++) {
        int s  = (a[k]-'0') + (b[k]-'0');
        int dk = c[k] - '0';
        if      (s     % 10 == dk) { r[k] = 0; q[k] = s     / 10; }
        else if ((s+1) % 10 == dk) { r[k] = 1; q[k] = (s+1) / 10; }
    }

    // Fragment [i,j] (0-indexed, i<=j) is a valid addition iff:
    //   (A) r[j] = 0          -- fragment starts with carry_in = 0
    //   (B) q[i] = 0          -- fragment ends with carry_out = 0
    //   (C) For all k in (i,j]: q[k] == r[k-1]  -- compatible carry chain
    //
    // Split positions into maximal "compatible segments" (no chain break).
    // Break between k-1 and k if: r[k]==-1 or r[k-1]==-1 or q[k]!=r[k-1].
    //
    // Within each segment, count pairs (i,j) with i<=j, q[i]=0, r[j]=0.
    // Running counter: scan left-to-right, cnt_q0 = # positions so far with q=0.
    // When r[j]=0, add cnt_q0 to answer.

    long long ans = 0;
    int seg_start = 0;

    auto process = [&](int lo, int hi) {
        long long cnt_q0 = 0;
        for (int j = lo; j <= hi; j++) {
            if (q[j] == 0) cnt_q0++;
            if (r[j] == 0) ans += cnt_q0;
        }
    };

    for (int k = 1; k <= n; k++) {
        if (k == n || r[k] == -1 || r[k-1] == -1 || q[k] != r[k-1]) {
            process(seg_start, k - 1);
            seg_start = k;
        }
    }

    cout << ans << "\n";
    return 0;
}