Problem:


Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

1 ≤ |S| ≤ 200000

S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.



Sample input:
1817181712114


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   d=0
   for i,j in enumerate(reversed(tmp)):
      d+=int(j)*10**(i)
      cnt[d%2019]+=1
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   d=0
   for i,j in enumerate(reversed(tmp)):
      d+=int(j)*10**(i)
      cnt[d%2019]+=1
   cnt=collections.Counter(cnt).items()
   for i,j in cnt:
      if i > 1:
         ans+=i*(i-1)//2*j
   print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
tmp=sys.stdin.readline().rstrip()
def main():
   cnt=[0]*2019
   cnt[0]+=1
   for i in reversed(range(len(tmp))):
      cnt[int(tmp[i:])%2019] += 1
   import collections
   cnt=collections.Counter(cnt).items()
   ans=0
   for i,j in cnt:
      if i > 1:
         ans+=i*(i-1)//2*j
   print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
tmp=input()
l=[int(tmp[i:]) for i in reversed(range(len(tmp)))]
cnt=[0]*2019
cnt[0] = 1
for i in l:
   cnt[i%2019] += 1
import collections
cnt=collections.Counter(cnt).items()
ans=0
for i,j in cnt:
   if i > 1:
      ans+=i*(i-1)//2*j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
tmp=input()
l=[int(tmp[i:]) for i in reversed(range(len(tmp)))]
cnt=[0]*2019
cnt[0] = 1
for i in l:
   cnt[i%2019] += 1
import collections
ans=0
for i in cnt:
   if i > 1:
      ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S = input()
MOD = 2019
div10 = 202  # modInverse(10, MOD). Note MOD is not prime so can't use FLT!


def solve1(S):
    # Naive implementation
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    # Instead of shuffling the entire counts, update how we index into counts instead
    # The cumulative shuffle function forward is something like a * index + b for some calculable a, b
    # Then indexing into counts[t][x] is same as indexing into counts[0][(x - b) / a]

    negPowTen = 1  # our a
    prefix = 0  # our b
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    # Alternative solution, precompute prefixes, p[i+1] == (10 * p[i] + S[i]) % MOD
    # Then you have for S = '1817181712114'
    # p[1] = 1
    # p[2] = 18
    # p[3] = 181
    # p[4] = 1817
    # etc
    # Then want to count all i j such that:
    # (p[j] - p[i] * pow(10, j - i)) % M == 0
    # Which is equivalent to
    # (p[j] * pow(10, -j) - p[i] * pow(10, -i) % M == 0
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    # Compute all suffixes instead
    # S     = '1817181712114'
    # suf[1] =             4
    # suf[2] =            14
    # suf[3] =           114
    # suf[4] =          2114
    #
    # Difference of suffixes is almost correct but has extra 10s.
    # For example 2114 to 114 is the string 2 but our difference returns 2000.
    # Luckily 2 and 5 aren't divisible by 2019 so the extra 10s don't matter when counting.
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen *= 10
    return total


#assert solve1(S) == solve2(S) == solve3(S) == solve4(S)
ans = solve4(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S = input()
MOD = 2019
div10 = 202  # modInverse(10, MOD). Note MOD is not prime so can't use FLT!


def solve1(S):
    # Naive implementation
    counts = Counter()
    total = 0
    for d in S:
        d = int(d)
        nextCounts = Counter()
        nextCounts[d] += 1
        for k, v in counts.items():
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    # Instead of shuffling the entire counts, update how we index into counts instead
    # The cumulative shuffle function forward is something like a * index + b for some calculable a, b
    # Then indexing into counts[t][x] is same as indexing into counts[0][(x - b) / a]

    negPowTen = 1  # our a
    prefix = 0  # our b
    counts = Counter()
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    # Alternative solution, precompute prefixes, p[i+1] == (10 * p[i] + S[i]) % MOD
    # Then you have for S = '1817181712114'
    # p[1] = 1
    # p[2] = 18
    # p[3] = 181
    # p[4] = 1817
    # etc
    # Then want to count all i j such that:
    # (p[j] - p[i] * pow(10, j - i)) % M == 0
    # Which is equivalent to
    # (p[j] * pow(10, -j) - p[i] * pow(10, -i) % M == 0
    negPowTen = 1
    total = 0
    prefix = 0
    counts = Counter()
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    # Compute all suffixes instead
    # S     = '1817181712114'
    # suf[1] =             4
    # suf[2] =            14
    # suf[3] =           114
    # suf[4] =          2114
    #
    # Difference of suffixes is almost correct but has extra 10s.
    # For example 2114 to 114 is the string 2 but our difference returns 2000.
    # Luckily 2 and 5 aren't divisible by 2019 so the extra 10s don't matter when counting.
    N = len(S)
    suf = 0
    powTen = 1
    counts = Counter()
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen *= 10
    return total


ans = solve2(S)
assert ans == solve3(S) == solve4(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def nC2(n):
    return n*(n-1)//2
    


n = input()
div = 2019
mods = [0]*2019
t = []

mods[0] += 1

t.append(0)
deg=1

for i in range(len(n)):
    t.append((t[-1] + int(n[-i-1])*deg)%2019)
    mods[t[-1]] += 1
    deg*=10

ans = 0
for i in range(2019):
    if mods[i]>1:
        ans += nC2(mods[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def deg(n):
    d=1
    for i in range(n):
        d = (d*10)%2019
    return d

def nC2(n):
    return n*(n-1)//2
    


n = input()
div = 2019
mods = [0]*2019
t = []

mods[0] += 1

t.append(0)

for i in range(len(n)):
    t.append((t[-1] + int(n[-i-1])*deg(i))%2019)
    mods[t[-1]] += 1

ans = 0
for i in range(2019):
    if mods[i]>1:
        ans += nC2(mods[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
dic={}
cur=0
power=1
for i in range(0,len(s)+1):
  s_int=len(s)-i-1
  if cur in dic:
    dic[cur]+=1
  else:
    dic[cur]=1
  try:
    num=int(s[s_int])
    cur+=num*10**power
    cur%=2019
    power+=1
  except IndexError:
    break

res=0
for i in range(len(dic)):
  t=dic.popitem()
  cc=t[1]
  res+=cc*(cc-1)//2
print(res)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
sur_list = [0 for i in range(2019)]
sur = 0
ans = 0

s.reverse()

for i in range(len(s)):
    sur_list[sur] += 1
    sur = (int(s[i]) * (10**i) + sur) % 2019
    ans += sur_list[sur]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=[int(x) for x in list(input())]
for c in range(len(s)-1,-1,-1):
    if c==len(s)-1:
        continue
    s[c]=((10**(len(s)-c-1))*s[c]+s[c+1])%2019
s.append(0)
s.sort()
h=[1]
d=s[0]
for c in range(1,len(s)):
    if s[c]!=d:
        h.append(1)
        d=s[c]
    else:
        h[-1]+=1
k=[(x*(x-1))//2 for x in h]
print(sum(k))

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    l = len(S)
    ans = 0
    if l <= 3:
        print("0")
        quit()
    for i in range(l - 3):
        for j in range(i, l):
            if int(S[i:j + 1]) % 2019 == 0:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    l = len(S)
    ans = 0
    for i in range(l):
        for j in range(i, l):
            if int(S[i:j + 1]) % 2019 == 0:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(S):
    ref = {}
    ret = 0
    for i in range(len(S) + 1):
        t = int(S[i:]) % 2019 if i < len(S) else 0
        ret += ref.get(t, 0)
        ref[t] = ref.get(t, 0) + 1
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

Submission status: Time Limit Exceeded

Solution code:
def solve(S):
    T = []
    for i in range(len(S)):
        T.append(int(S[i:]) % 2019)
    T.append(0)

    ref = {}
    ret = 0
    for t in T:
        ret += ref.get(t, 0)
        ref[t] = ref.get(t, 0) + 1
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

Submission status: Time Limit Exceeded

Solution code:
def solve(S):
    ret = 0
    for i in range(len(S)):
        for j in range(i, len(S)):
           ret += 1 if not int(S[i: j + 1]) % 2019 else 0
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

Submission status: Time Limit Exceeded

Solution code:
s=input()
s=s[::-1]
n=len(s)
cnt=[0]*2019
cnt[0]+=1
c=0
for i in range(n):
  c+=int(s[i])*(10**i)%2019
  cnt[c%2019]+=1
ans=0
for i in cnt:
  if i<=1:
    pass
  else:
    ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*2019
cnt[0]+=1
c=0
for i in range(n):
  c+=s[i]*(10**i)%2019
  cnt[c%2019]+=1
ans=0
for i in cnt:
  if i<=1:
    pass
  else:
    ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*(n+1)
cnt[0]=s[0]%2019
c=s[0]
for i in range(1,n):
  c+=s[i]*(10**i)%2019
  cnt[i]=c%2019
d={}
for i in cnt:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*(n+1)
cnt[0]=s[0]%2019
c=s[0]
for i in range(1,n):
  c+=s[i]*(10**i)
  cnt[i]=c%2019
d={}
for i in cnt:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
m = [0 for _ in range(2019)]
m[0] = 1
for i in range(len(s)):
    t = int(s[i:])
    m[t % 2019] += 1
print(sum([int(x * (x - 1) / 2) for x in m if x > 1]))

Submission status: Time Limit Exceeded

Solution code:
s=input()
b=0
dp=[]
for i in range(len(s)):
    dp.append([0]*2019)
dp[0][int(s[0])]+=1
for i in range(len(s)-1):
    for j in range(2019):
        dp[i+1][(10*j+int(s[i+1]))%2019]+=dp[i][j]
    dp[i+1][int(s[i+1])]+=1
for i in range(len(s)):
    b+=dp[i][0]
print(b)

Submission status: Time Limit Exceeded

Solution code:
s = input()
m = {0: 0}
for i in range(len(s)):
    t = int(s[i:])
    a = t % 2019
    if a in m:
        m.update({a: m[a] + 1})
    else:
        m.update({a: 0})
ans = 0
for _, v in m.items():
    ans += v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    ans = 0
    t = {}
    for _s in map(int, string):
        t = {(10 * i + _s) % 2019: v for i, v in t.items()}
        t[_s] = t[_s] + 1 if _s in t.keys() else 1
        if 0 in t.keys():
            ans += t[0]
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
s=input()
a=0
m={}
for i in range(len(s)):
  b=int(s[len(s)-1-i])*10**i+a
  b=b%2019
  a=b
  if b in m:
    m[b]+=1
  else:
    m[b]=1
if 0 in m:
  sum=m[0]
else:
  sum=0
for i in m:
  sum+=m[i]*(m[i]-1)/2
print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
a=0
t=1
d=[1]+[0]*2018
 
for i in range(n):
    a+=int(s[n-1-i])*t
    a%=2019
    t*=10
    #t%=2019
    
    d[a]+=1

ans=0
for i in d:
    ans+=i*(i-1)//2
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
s = input()
n = len(s)
dp = [0] * n
mod = 2019
for i in range(n):
    m = int(s[i]) * pow(10, n - i - 1, mod) % mod
    dp[i] = m

dp = [0] + dp
for i in range(n):
    dp[i + 1] += dp[i]

ans = 0
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        total = dp[j] - dp[i]
        if total % mod == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
s = input()
n = len(s)
dp = [0] * n
mod = 2019
for i in range(n):
    m = int(s[i]) * pow(10, n - i - 1, mod) % mod
    dp[i] = m

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        total = sum(dp[i:j + 1])
        if total % mod == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

mod_count = [0] * 2019

d = 10

#for i in range(len(S)):
#    S_mod[i] = int(S[i:len(S)])%2019

for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d *= 10
    
#print(S_mod)

for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))

Submission status: Time Limit Exceeded

Solution code:
S = input()

result = []

for i in range(len(S) - 3):
    for j in range(i + 3, len(S)):
        if int(S[i:j+1]) % 2019 == 0:
            result.append([i + 1, j + 1])

print(len(result))

Submission status: Time Limit Exceeded

Solution code:
S = input()

result = []

for i in range(len(S)):
    for j in range(i + 3, len(S)):
        if int(S[i:j+1]) % 2019 == 0:
            result.append([i + 1, j + 1])

print(len(result))

Submission status: Time Limit Exceeded

Solution code:
S = input()

#S_mod = [0] * (len(S)+1)

mod_count = [0] * 2019
mod_count[0] = 1

for i in range(len(S)):
    mod_count[int(S[i:len(S)])%2019] += 1
    
#print(S_mod)

#for i in range(len(S_mod)):
#    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))

Submission status: Time Limit Exceeded

Solution code:
S = input()

S_mod = [0] * (len(S)+1)

mod_count = [0] * 2019

for i in range(len(S)):
    S_mod[i] = int(S[i:len(S)])%2019
    
#print(S_mod)

for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))

Submission status: Time Limit Exceeded

Solution code:
s = int(input())

n = 0
while True:
    if s//(10**n)==0:
        break
    n+=1

i = 1
m = list()
while i<=n:
    m.append((s%(10**i))%2019)
    i+=1

i = 0
ans = 0
while i<n:
    j = 1
    while i+j<n:
        if m[i] == m[i+j]:
            ans += 1
        j+=1
    if m[i] == 0:
        ans += 1
    i+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
l = len(S)
count = 0
for i in range(len(S)-4):
  for j in range(i+4,len(S)):
    if int(S[i:j+1])%2019 == 0:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

S_len = len(S)
count = 0
for l_scope in range(5, S_len+1):
    for p_scope in range(0, S_len - l_scope + 1):
        if int(S[p_scope:p_scope+l_scope]) % 2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

S_len = len(S)
count = 0
for l_scope in range(4, S_len+1):
    for p_scope in range(0, S_len - l_scope + 1):
        if int(S[p_scope:p_scope+l_scope]) % 2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

for i in range(len(S)-3):
  for j in range(i+3, len(S)):
    T = int(S[i:j+1])
    #print(T)
    if T % 2019 == 0:
      count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

S = S[::-1]

A = [int(S[i]) * (10**i) % 2019 for i in range(len(S))]
# print(A)

S = [sum(A[:i]) % 2019 for i in range(len(A)+1)]

# print(S)

from collections import defaultdict
chose = defaultdict(int)
for s in S:
    chose[s] += 1

# print(chose)

ans = 0
for ch in chose.values():
    if ch == 1:
        continue
    ans += cmb(ch,2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
from scipy.special import comb

S = S[::-1]

A = [int(S[i]) * (10**i) % 2019 for i in range(len(S))]
# print(A)

S = [sum(A[:i]) % 2019 for i in range(len(A)+1)]

# print(S)

from collections import defaultdict
chose = defaultdict(int)
for s in S:
    chose[s] += 1

# print(chose)

ans = 0
for ch in chose.values():
    ans += comb(ch, 2, exact=True)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
D=[0]*2019
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*10**keta)%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

count = 0
for i in range(len(s)-3):
    for j in range(i+4,len(s)+1):
        tmp_s = s[i:j]
        #print(tmp_s)
        if int(tmp_s) % 2019 == 0: #2019で割り切れる
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()

count = 0
for i in range(len(s)-3):
    for j in range(i+4,len(s)):
        tmp_s = s[i:j+1]
        if len(tmp_s) >=4:
            if int(tmp_s) % 2019 == 0: #2019で割り切れる
                count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x[i]=a%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x[i]=a%2019
c=Counter(x)
cc=c.most_common()
ans = c[0]
for i in range(len(cc)):
    b=cc[i][1]
    ans += b*(b-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def combi(n,r):
    if n==0 or n==1:
        return 0
    ans=1
    for i in range(r):
        ans*=(n-i)
    for i in range(1,r+1):
        ans//=i
    return ans

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x[i]=a%2019
c=Counter(x)
cc=c.most_common()
ans = c[0]
for i in range(len(cc)):
    ans += combi(cc[i][1],2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def combi(n,r):
    if n==0 or n==1:
        return 0
    ans=1
    for i in range(r):
        ans*=(n-i)
    for i in range(1,r+1):
        ans//=i
    return ans

n = list(input())
n.reverse()
x = []
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x.append(a%2019)
c=Counter(x)
cc=c.most_common()
ans = c[0]
for i in range(len(cc)):
    ans += combi(cc[i][1],2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def combi(n,r):
    if n==0 or n==1:
        return 0
    ans=1
    for i in range(1,n+1):
        ans*=i
    for i in range(1,r+1):
        ans//=i
    return ans

n = list(input())
n.reverse()
x = []
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x.append(a%2019)
c=Counter(x)
ans = c[0]
for i in range(1,2020):
    ans += combi(c[i],2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(str(input()))
ans = 0
ans += S.count('0')

if len(S) > 4:
  for i in range(len(S)-4):
    for j in range(i+4,len(S)+1):
      if int(''.join(S[i:j])) % 2019 == 0:
        ans += 1
else:
  if int(''.join(S))%2019==0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    ans = 0
    _t = [0] * 2019
    for _s in map(int, string):
        t = [0] * 2019
        for i, t_ in enumerate(_t):
            if t_:
                t[(10 * i + _s) % 2019] += t_
        t[_s] += 1
        _t = t
        ans += _t[0]
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
ls=[int(s[i:])%2019 for i in range(0,n)]
ls.append(0)
p=0
for i in range(0,n-3):
  for j in range(i+3,n):
    if ls[i]==ls[j+1]:p+=1
    else:pass

print(p)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    s = input()

    n = 2019
    l = [0]
    for i, x in enumerate(s[::-1]):
        y = l[-1] + int(x) * pow(10, i)
        z = y % n
        l.append(z)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
MOD = 2019
def main():
    S = input()
    dp = [0] * (len(S)+1)
    for i in range(len(S)):
        dp[i+1] = (int(S[-1-i])*(10**i) + dp[i]) % MOD
    d = defaultdict(int)
    for i in range(len(S)+1):
        d[dp[i]] += 1
    output = 0
    for i in d.keys():
        output += (d[i] * (d[i]-1) // 2)
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    from math import factorial as f
    s = input()
    l = len(s)
    n = 2019
    t = [int(s[-i:]) % n for i in range(1, l + 1)]
    c = Counter(t)
    ans = 0
    for k, v in c.items():
        if v > 1:
            c = f(v) // f(v - 2) // 2
            ans += c
        if k == 0:
            ans += v
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    ans = 0
    n = len(s)
    m = 2019
    for i in range(n - 3):
        for j in range(i + 3, n):
            t = int(s[i:j + 1])
            if t % m == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 2019

cum = [0]*n
cum[n-1] = int(s[-1]) % mod
d = 10
for i in range(0, n-1)[::-1]:
    a = int(s[i]) * d % mod
    cum[i] = (cum[i+1]+a) % mod
    d *= 10
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 2019
dp = [0 for i in range(n)]
for i,c in enumerate(s):
    dp[i] = int(c) % mod

cum = [0]*n
cum[0] = dp[0]
cum[n-1] = int(s[-1]) % mod
d = 10
for i in range(0, n-1)[::-1]:
    a = int(s[i])* d % mod
    cum[i] = (cum[i+1]+a) % mod
    d *= 10
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 2019
dp = [0 for i in range(n)]
for i,c in enumerate(s):
    dp[i] = int(c) % mod

cum = [0]*n
cum[0] = dp[0]
cum[n-1] = int(s[-1]) % mod
for i in range(0, n-1)[::-1]:
    a = int(s[i])*10**(n-1-i) % mod
    cum[i] = (cum[i+1]+a) % mod
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np 
#import bisect 
S=input() 
l=len(S) 
p=0 
#lock=np.arange(1,100)*2019 
for i in range(0,l-3): 
  for j in range(i+3,l+1): 
    se=int(S[i:j]) 
    #index=bisect.bisect_left(lock, se) 
    if se%2019==0: p+=1 
    else: pass 
print(p)

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
S = str(S)
n = len(str(S))
nnn = 0

if n>4:
    for i in range(n-3):
        for j in range(i+3, n):
            nn = int(S[i:j+1])
            
            if nn % 2019 == 0:
                nnn += 1
print(nnn)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

lengh = len(S)

cou = 0
for i in range(0, lengh - 3):
    total = 0
    for j in range(i, lengh):
        total *= 10
        total += int(S[j])
        if total % 2019 == 0:
            cou += 1
print(cou)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S=input()
    ans=0
    for i in range(len(S)-3):
        for j in range(i+3,len(S)):
            if int(S[i:j+1])%2019==0: ans+=1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input

for i in range(10 ** 10):
  a = 1 + 1

Submission status: Time Limit Exceeded

Solution code:
# D
# Multiple of 2019
import itertools

s = input()

d = len(s)

_list = [None]*d
_map = [0]*2019

ans = 0

for i in range(d):
    _tmp = int(s[i:])%2019
    _list[i] = _tmp
    if _tmp == 0:
        ans += 1
    elif _map[_tmp] ==1:
        ans += 1
    _map[_tmp] = 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D
# Multiple of 2019
import itertools

s = input()

d = len(s)

_list = [None]*d

ans = 0

for i in range(d):
    _tmp = int(s[i:])%2019
    _list[i] = _tmp
    if _tmp == 0:
        ans += 1

for _ in itertools.combinations(_list,2):
    if _[0] == _[1]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
S_len = len(S)
S = int(S)
count = 0

for i in range(S_len):
  for j in range(i+3,S_len):
    x = S  % 10**(S_len-i)
    x = x // 10**(S_len-j-1)
    if x % 2019 == 0:
      count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
S_len = len(S)
S = int(S)
count = 0

for i in range(S_len):
  for j in range(i,S_len):
    x = S  % 10**(S_len-i)
    x = x // 10**(S_len-j-1)
    if x % 2019 == 0:
      count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# D
# Multiple of 2019

s = input()

d = len(s)

ans = 0

if d < 5:
    if int(s)%2019 == 0:
        print("1")
    else:
        print("0")
else:
    for j in range(4,d,1):
        for i in range(j-3):
            _tmp = int(s[i:j+1])
            if _tmp % 2019 == 0:
                ans +=1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

count = 0

for i in range(len(S)):
  for j in range(i,len(S)):
    x = int(S[i:j+1])
    if x % 2019 == 0:
      count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# D
# Multiple of 2019

s = input()

d = len(s)

ans = 0

for j in range(d):
    for i in range(j):
        _tmp = int(s[i:j+1])
        if _tmp % 2019 == 0:
            ans +=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

a = input()
n = len(a)

res = [-1] * (n+1) 
res[n] = 0
for i in range(n-1, -1, -1):
    res[i] = (res[i+1] + 10**(n-i-1) * int(a[i]) % 2019) % 2019

c = Counter(res)
print(int(sum([i*(i-1)/2 for i in c.values()])))

Submission status: Time Limit Exceeded

Solution code:
s= input()
count = 0
for i in range(len(s)-3):
    for j in range(i+4,len(s)+1):
        if int(s[i:j])%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
count = 0
temp = input()
for i in range(0,len(temp)-3):
    for j in range(i+4,len(temp)+1):
        if int(temp[i:j])%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
t = [0]*(n+1)
d = 1
l = [0]*2019

t[n] = 0
t[n-1] = int(S[n-1])

l[0] += 1

for i in range(n-1, -1, -1):
    t[i] = int(S[i]+str(t[i+1]))
    l[t[i]%2019] += 1 

print(sum(map(lambda x: x*(x-1)//2, l)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
a = int(S)
l = [0]*2019
t = pow(10, n-1)

l[a%2019] += 1

for i in range(n):
    a = a - int(S[i])*t
    l[a%2019] += 1
    t = t // 10

ans = 0
for i in l:
    ans += i*(i-1)//2
print(ans)