fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[100005];
  4. int main() {
  5.     string s; cin >> s;
  6.     int n = s.length(); s = " " + s;
  7.     map<int,map<int,int>> mp;
  8.     for (int i=1; i<=n; i++) {
  9.         a[i] = a[i-1] + (s[i]-'0');
  10.     }
  11.     for (int i=n; i>=1; i--) {
  12.         for (int j=0; j<3; j++) mp[i][j] = mp[i+1][j];
  13.         mp[i][a[i] % 3]++;
  14.     }
  15.     int cnt = (a[n]%3==0) - 1;
  16.     for (int L=1; L<=n; L++) {
  17.         cnt += mp[L][(a[n] + a[L-1]) % 3];
  18.     }
  19.     cout << cnt;
  20. }
Success #stdin #stdout 0.01s 5400KB
comments (?)
stdin
copy 
1005
stdout
copy 
4
https://ideone.com/ZTUbQ3
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!