algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (887B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <string>
      4 
      5 int main() {
      6     std::string a, b;
      7     std::cin >> a;
      8     std::cin >> b;
      9     long long res = 0;
     10     // inclusive prefix sum
     11     std::vector<long long> prefixSum {};
     12     std::vector<long long> prefixSumZero {};
     13     long long sum = 0;
     14     long long sumZero = 0;
     15 
     16     for(int i = 0; i < b.size(); ++i) {
     17         if(b[i] == '1') {
     18             sum += 1;
     19         } else {
     20             sumZero += 1;
     21         }
     22 
     23         prefixSum.push_back(sum);        
     24         prefixSumZero.push_back(sumZero);
     25     }
     26 
     27     for(int x = 0; x < a.size(); ++x) {
     28         if(a[x] == '0') {
     29             res += prefixSum[(b.size()-1) - (a.size() - 1 - x)] - prefixSum[x] + (b[x] == '1');
     30         } else {
     31             res += prefixSumZero[(b.size()-1) - (a.size() - 1 - x)] - prefixSumZero[x] + (b[x] == '0');
     32         }
     33     }
     34     std::cout << res << std::endl;
     35 }