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
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    U = set([0])
    dic = {0:1} # value:count
    ans = 0
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (10**(rev_i+1))
        u = V[rev_i+1] % K
        if u in U:
            dic[u] += 1
            cnt = dic[u]
            ans -= (cnt-1) * (cnt-2) // 2
            ans += cnt * (cnt-1) // 2
        else:
            dic[u] = 1
            U.add(u)


    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)

    ans //= 2
    ans %= K
    
    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = len(s)

m = [0 for i in range(2019)]
m[0] = 1
a = 0
for i in reversed(range(0, t)):
    a += 10**(t-i-1) * int(s[i])
    a = a % 2019
    m[a] += 1

def triangle(n):
    if n > 1:
        return n * (n-1) // 2
    else:
        return 0

p = list(map(triangle, m))
# print(p)
print(sum(p))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
t = len(s)

m = np.array([0])
a = 0
for i in reversed(range(0, t)):
    a += 10**(t-i-1) * int(s[i])
    a = a % 2019
    m = np.append(m, a)

n = np.sort(m)

c = 0
d = 0

for i in range(t-1):
    if n[i] == n[i+1]:
        c += 1
        d += c
    else:
        c = 0

print(d)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = len(s)

m = [0]
a = 0
for i in reversed(range(0, t)):
    a += 10**(t-i-1) * int(s[i])
    a = a % 2019
    m.append(a)

n = sorted(m)

c = 0
d = 0

for i in range(t-1):
    if n[i] == n[i+1]:
        c += 1
        d += c
    else:
        c = 0

print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
S = input()
count = 0

if len(S) <= 3:
    print("0")
    sys.exit()

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:
s = input()
t = len(s)

m = [0]
a = 0
for i in reversed(range(0, t)):
    a += 10**(t-i-1) * int(s[i])
    a = a % 2019
    m.append(a)

n = sorted(m)

c = 0
d = 0

for i in range(t-1):
    if n[i] == n[i+1]:
        c += 1
        d += c
    else:
        c = 0

print(d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import Counter

def main():
    S = input()
    N = len(S)
    T = [0] * (N+1)
    
    for i in range(N-1,-1,-1):
        T[i] = (T[i+1] + int(S[i]) * (10**(N-i))) % 2019
    l = Counter(T)
    ans = 0
    for v in l.values():
        ans += v * (v-1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(len(s)-3):
    for j in range(4+i,len(s)+1):
        s2 = int(s[i:j])
        if s2 % 2019 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
s = input()
n = len(s)
d = dict()

if len(s) <= 3:
    print(0)
    exit()


suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])
suffix_rems[-2] = int(s[-2:])
suffix_rems[-3] = int(s[-3:])

rems_d = dict()
# rems_d[0] = [n]
# rems_d[int(s[-1])] = [n-1]
# rems_d[int(s[-2:])] = [n-2]
# rems_d[int(s[-3:])] = [n-3]
rems_d[0] = 1
rems_d[int(s[-1])] = 1
rems_d[int(s[-2:])] = 1
rems_d[int(s[-3:])] = 1


special_keys = set()
for i in range(n-3)[::-1]:
    rem = (10**(n-i-1) * int(s[i]) + suffix_rems[i + 1])%2019

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)

    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

ans = 0
for key in special_keys:
    t = rems_d[key]
    ans += (t*(t-1))//2


print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D
S = str(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 = count+1
        else:
            pass
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
s=str(input())
s1=len(s)
k=0
a=0
p=list()
if s1<4:
    print(0)
    sys.exit()
for i in range(s1):
    b=(int(s[s1-i-1])*10**i)%2019
    a=a+b
    p.append(a%2019)
for i in range(1,2019):
    l=p.count(i)
    if l>=2:
        k=k+l-1
x=p.count(0)
print(int(k+x*(x+1)/2))

Submission status: Time Limit Exceeded

Solution code:
import sys
s=str(input())
s1=len(s)
k=0
a=0
p=list()
if s1<4:
    print(0)
    sys.exit()
for i in range(s1):
    b=(int(s[s1-i-1])*10**i)%2019
    a=a+b
    p.append(a%2019)
for i in range(s1):
    a=p[0]
    if a==0:
        k=k+1
    p.remove(a)
    k=k+p.count(a)
print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys
s=str(input())
s1=len(s)
k=0
p=list()
if s1<4:
    print(0)
    sys.exit()
for i in range(s1):
    b=(int(s[s1-i-1])*10**i)%2019
    p.append(b)
for i in range(s1):
    for l in range(i+1,s1+1):
        if sum(p[i:l])%2019==0:
            k=k+1
print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
s = list(input())
lsts = deque()
kai = 0
cou = 0
for i in range(len(s)):
  s[i] = int(s[i])
s.reverse()
s = deque(s)
cou = 0
le = len(s)
st = 0

for i in s:
  st += i * (10 ** kai)
  amari = st % 2019
  if amari == 0:
    cou += 1
  else:
    lsts.append(amari)  
  kai += 1

while lsts:
  atai = lsts.pop()
  kosu = lsts.count(atai)
  if kosu != 0:
    cou += int(kosu * (kosu+1) / 2)
    for i in range(kosu):
      lsts.remove(atai)

print(cou)

Submission status: Time Limit Exceeded

Solution code:

def main():
    s = input()
    cnt = 0
    for i in range(len(s) - 4):
        for j in range(i + 4, len(s)):
            if int(s[i:j + 1]) % 2019 == 0:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
s = deque(input())
lsts = deque()

for i in range(len(s)):
  s[i] = int(s[i])
cou = 0

for i in range(100):
  lsts = deque(s)
  l = 2019*(i+1)
  llen = len(str(l))
  
  for j in range(len(s)-llen+1):
    st = 0
    
    for k in range(llen):
      st += lsts[-(1+k)] * (10**k)
      
    lsts.pop()
    if st == l:
      cou += 1

print(cou)

Submission status: Time Limit Exceeded

Solution code:

def main():
    s = input()
    cnt = 0
    for i in range(len(s) - 3):
        for j in range(i + 3, len(s)):
            if int(s[i:j + 1]) % 2019 == 0:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
T = set([0])
for i in range(len(s)):
    T.add(int(s[i::]) % 2019)

print(len(s)+1-len(T))

Submission status: Time Limit Exceeded

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

print(len(T)-len(set(T)))

Submission status: Time Limit Exceeded

Solution code:
s = input()
T = [0]
for i in range(len(s)):
    T.append(int(s[i::]))

T = [t % 2019 for t in T]
print(len(T)-len(set(T)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s=input()[::-1]
m=len(s)
DP=[0]
word=""

for i in s:
    word=i+word
    DP.append(int(word)%2019)

DP=Counter(DP)
ans=0
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s=input()[::-1]
m=len(s)
DP=[0]
word=""

for i in s:
    word +=i
    DP.append(int(word[::-1])%2019)

DP=Counter(DP)
ans=0
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s=input()
m=len(s)
DP=[""]

for i in range(m):
    DP.append(DP[-1]+s[-(i+1)])

for i in range(1,len(DP)):
    DP[i]=int(DP[i][::-1])%2019
DP.append(0)
DP=Counter(DP)

ans=0
for v,m in DP.items():
    if m>=2:ans +=m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s=input()
m=len(s)
DP=[0]

for i in range(m):
    DP.append(int(s[m-(i+1):]))

for i in range(len(DP)):
    DP[i]=DP[i]%2019
DP=Counter(DP)

ans=0
for v,m in DP.items():
    if m>=2:ans +=m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
s=input()
s1=len(s)
k=0
if s1<4:
    print(0)
    sys.exit()
for i in range(s1-3):
    a=int(s[s1-4-i:s1-i])
    c=a
    if c%2019==0:
            k=k+1
    for l in range(i+4,s1):
        b=int(s[s1-l-1])
        c=c+b*10**(l-i)
        if c%2019==0:
            k=k+1
print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys
s=input()
s1=len(s)
k=0
if s1<4:
    print(0)
    sys.exit()
for i in range(s1-3):
    if i+4>s1:
        break
    for l in range(i+4,s1+1):
        ss=int(s[i:l])
        if ss%2019==0:
            k=k+1
print(k)

Submission status: Time Limit Exceeded

Solution code:
s = input()

def difnum2(a, b, dif):
    d = []
    for i in range(a, b - dif + 1):
        for j in range(i + dif, b + 1):
            d.append([i, j])
    return d

d = difnum2(1, len(s), 3)
n = 0
tf = 0
for i in range(len(d)):
    if (tf > 0) & (d[i][1] < len(s) - 4):
        tf -= 1
        continue
    cur = d[i]
    ps = int(s[cur[0] - 1 : cur[1]])
    if ps % 2019 == 0:
        n += 1
        tf = 3

print(n)

Submission status: Time Limit Exceeded

Solution code:
s = input()

count = s.count('0000') +s.count('2019') + s.count('4038') + s.count('8076')

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0

for i in range(0, 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:
s = input()

def difnum2(a, b, dif):
    d = []
    for i in range(a, b - dif + 1):
        for j in range(i + dif, b + 1):
            d.append([i, j])
    return d

d = difnum2(1, len(s), 3)
n = 0
for i in range(len(d)):
    cur = d[i]
    ps = int(s[cur[0] - 1 : cur[1]])
    if ps % 2019 == 0:
        n += 1

print(n)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = {0:1}
memo = [0]
for ind, s in enumerate(S[::-1]):
    memo.append(int(S[-ind-1:]) % 2019)
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = {0:1}
memo = [0]
for ind, s in enumerate(S[::-1]):
    memo.append((memo[-1]+int(s)*(10**ind))%2019)
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    for i, e in enumerate(reversed(S)):
        rmd = (int(e)*10**i + rmd) % 2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    L = len(S)
    for i in range(L):
        rmd = (int(S[L-i-1])*10**i + rmd) % 2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
n=0
i=0
a=[0]*len(S)
for s in S[::-1]:
  n+=int(s)*10**i
  a[i]=n%2019
  i+=1


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
s=0
a=[0]*len(S)
for i in range(len(S)):
  s+=int(S[len(S)-i-1])*10**i
  a[i]=s%2019


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
s=int(S[len(S)-1])
a=[0,s]
for i in range(1,len(S)):
  s+=int(S[len(S)-i-1])*10**i
  a.append(s%2019)
q={}
for i in range(len(a)):
  if a[i] in q:
    q[a[i]]+=1
  else:
    q[a[i]]=1
c=0

for value in q.values():
  c+=value*(value-1)/2
print(int(c))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

s = input()

ans = 0
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        # print(s[i:j])
        n = s[i:j]
        if int(n) % 2019 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
 
cnt = 0
x = set()
for i in range(len(s)-3):
  for j in range(i+4,len(s)+1):
    x.add(s[i:j])


for xx in x:    
  if int(xx) % 2019 == 0:
    for j in range(len(s)-len(xx)+1):
      if s[j:len(xx)+j] == xx :
        cnt += 1
 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

cnt = 0
for i in range(len(s)-3):
  if s[i] == "0" :
    continue
  if  s[i] in ["1","3","5","7","9"]:
    x = 5
  else :
    x = 4
  for j in range(i+x,len(s)+1):
    if int(s[i:j]) % 2019 == 0:
      cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

cnt = 0
for i in range(len(s)-3):
  for j in range(i+1,len(s)+1):
    if int(s[i:j]) % 2019 == 0:
      cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=[int(s) for s in input()]

ans=0

for i in range(len(s)-4):
  nums=[s[i],s[i+1],s[i+2],s[i+3]]
  for j in range(len(s)-3-i):
    #print(nums)
    if sum(nums)%3==0:
      c=0
      for a,b in enumerate(reversed(nums)):
        c+=b*(10**a)
      if c%673==0:
        ans+=1
      try:
        nums.append(s[i+j+4])
      except:
        pass
    else:
      try:
        nums.append(s[i+j+4])
      except:
        pass
    
      
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=[int(s) for s in input()]

ans=0

for i in range(len(s)-4):
  num=s[i]*1000+s[i+1]*100+s[i+2]*10+s[i+3]
  for j in range(len(s)-3-i):
    #print(num)
    if num % 2019 ==0:
      ans+=1
    try:
      num=num*10+s[i+j+4]
    except:
      pass
      
    
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a=0
S=input()
N=len(S)
for i in range(N-3):
  for j in range(i+3,N):
    if sum(list(map(int,S[i:j+1])))%3==0:
      if int(S[i:j+1])%673==0:
        a=a+1
print(a)

Submission status: Time Limit Exceeded

Solution code:
a=0
S=input()
N=len(S)
for i in range(N-3):
  for j in range(i+3,N):
    A=int(S[i:j+1])
    if A%2019==0:
      a=a+1
print(a)

Submission status: Time Limit Exceeded

Solution code:
S=input()

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

print(len(comb))

Submission status: Time Limit Exceeded

Solution code:
S=input()

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

print(len(comb))

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
listmod = [0]*2019
for i in range(1,len(S)+1):
    if(i == 1):
        T = int(S[-1])
        listmod[T] = 1
        mod2 = T
    else:
        T = int(S[-i])
        mod1 = (T*10**(i-1)%2019 + mod2)%2019
        listmod[mod1] += 1
        mod2 = mod1
for i in range(2019):
    if(i == 0):
        ans += listmod[0]
    else:
        n = listmod[i]
        ans += int((n-1)*n/2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
listmod = [0]*2019
for i in range(1,len(S)+1):
    T = int(S[-i:])
    modT = T%2019
    listmod[modT] += 1
for i in range(2019):
    if(i == 0):
        ans += listmod[0]
    else:
        if(listmod[i] > 1):
            ans += listmod[i] - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0


for i in range(0,len(s)):
    sub = ""
    for j in range(i,len(s)):
        sub+=s[j]
        if int(sub)%2019==0:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
from collections import deque
z = deque([0])
for i in range(len(s)):
    z.append(int(s[i:])%2019)

from collections import Counter
q = Counter(z)

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
z = [0]
for i in range(len(s)):
    z.append(int(s[i:])%2019)

from collections import Counter
q = Counter(z)

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

Submission status: Time Limit Exceeded

Solution code:
s=[int(x) for x in input()]
L=[]
sum=0
for i in range(len(s)):
    t=s[i]*(10**(len(s)-i))
    sum += t
    L.append(sum%2019)
L.sort()

ans=0
count=1
for i in range(len(L)-1):
    if L[i]==L[i+1]:
        count += 1
    else:
        if L[i]==0:
            count += 1
        if count>1:
            ans += count*(count-1)//2
        count=1
if count>1:
    ans += count*(count-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = str(input())
list =[]
for i in range(len(N)-3):
    for j in range(i+3,len(N)+1):
        if int(N[i:j])%3!=0:
            continue
        if int(N[i:j])%673==0:
            list.append((i+1,j))

print(len(list))

Submission status: Time Limit Exceeded

Solution code:
N = str(input())
list =[]
for i in range(len(N)-3):
    for j in range(i+3,len(N)+1):
        if int(N[i:j])%2019==0:
            list.append((i+1,j))

print(len(list))

Submission status: Time Limit Exceeded

Solution code:
N = str(input())
list =[]
for i in range(len(N)-1):
    for j in range(i+1,len(N)+1):
        if int(N[i:j])%2019==0:
            list.append((i+1,j))

print(len(list))

Submission status: Time Limit Exceeded

Solution code:
s=[int(x) for x in input()]
L=[]
sum=0
for i in range(len(s)):
    t=s[i]*(10**(len(s)-i))
    sum += t
    L.append(sum%2019)
import collections
L=collections.Counter(L)
L=L.most_common()
ans=0
for i in L:
    if i[0]==0:
        ans += i[1]*(i[1]+1)//2
    elif i[1]>1:
        ans += i[1]*(i[1]-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

S = sys.stdin.readline().strip()

N = 2019
L = len(S)
dp = [[0 for _ in range(N)] for _ in range(L) ]
for i in range(L):
    t = int(S[i])
    dp[i][t] = 1

    for j in range(N):
        dp[i][(j*10 + t)%N] += dp[i-1][j]

res = 0
for i in range(L):
    res += dp[i][0]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

S = sys.stdin.readline().strip()

N = 2019
prev, curr = {}, {}
res = 0
for i in range(len(S)):
    curr = {}
    curr[int(S[i])] = 1
    for k in prev.keys():
        tmp = (k*10 + int(S[i])) % N
        if tmp not in curr: curr[tmp] = 0
        curr[tmp] += prev[k]
    if 0 in curr: res += curr[0]
    prev = curr
print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  #d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0

## 4桁
for i in range(0, len(S)-3):
  for j in range(i+3, len(S)):
    if int(S[i:j+1]) % 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(len(S)):
        if j-i >= 4:
            count += (int(S[i:j+1])%2019 == 0)
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

# for i in range(10):
#     print(i * 2019)
#     X = str(i * 2019)
#     S = 0
#     for j in range(len(X)):
#         S += int(X[j])
#     print(S)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np
def main():
    s = input()
    n = len(s)
    d = np.zeros(2019,np.int64)
    ans = 0
    num = 0
    d[0] += 1
    for i in reversed(range(n)):
        num += int(s[i]) * 10 ** (n - 1 - i)
        #print(num, num % 2019, i)
        mod = num % 2019
        ans += d[mod]
        d[mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
s = input()
count = 0

for i,j in itertools.combinations(range(0,len(str(s))+1),2):
    if int(s[i:j]) % 2019 ==0:
        count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():
    s = input()
    n = len(s)
    d = defaultdict(int)
    ans = 0
    num = 0
    d[0] += 1
    for i in reversed(range(n)):
        num += int(s[i]) * 10 ** (n - 1 - i)
        #print(num, num % 2019, i)
        mod = num % 2019
        ans += d[mod]
        d[mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():
    s = input()
    n = len(s)
    d = defaultdict(int)
    num = 0
    d[0] += 1
    for i in reversed(range(n)):
        num += int(s[i]) * 10 ** (n - 1 - i)
        #print(num, num % 2019, i)
        d[num % 2019] += 1

    ans = 0
    for _, cnt in d.items():
        ans += cnt * (cnt - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    num += int(S[i]) * d
    num %= 2019
    # num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1
    d *= 10

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    d = 10 ** (N-i-1)
    num += int(S[i]) * d
    num %= 2019
    # num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    num += int(S[i]) * 10 ** (N-i-1)
    num %= 2019
    # num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
T = [0] * (N+1)
cnt = [0]*2019
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    T[i] = (T[i+1] + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[T[i]] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
T = [0] * (N+1)
cnt = {i:0 for i in range(2019)}
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    T[i] = (T[i+1] + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[T[i]] += 1

ans = 0
for i in range(2019):
    m = cnt[i]
    ans += m * (m-1) // 2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(1,len(s)+1):
    top = int(s[-i:])
    a = top % 2019
    for j in range(i):
        if not j:
            bot = 0
        else:
            bot = int(s[-j:])
        
        if bot % 2019 == a:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(1,len(s)+1):
    top = int(s[-i:])
    for j in range(i):
        if not j:
            bot = 0
        else:
            bot = int(s[-j:])
        
        if top % 2019 == bot % 2019:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
for i in range(N-1,-1,-1): 
  s=int(S[i])*(10**(N-1-i))
  mod2+=s%2019
  mod2=mod2%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(N-1,-1,-1): 
  s+=int(S[i])*(10**(N-1-i))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(N-1,-1,-1): 
  s+=int(S[i])*(10**(N-1-i))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(N-1,-1,-1): 
  s+=int(S[i])*(10**(N-1-i))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n,r):
  return factorial(n)//factorial(n-r)//factorial(r)
S=input()
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(N-1,-1,-1): 
  s+=int(S[i])*(10**(N-1-i))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=comb(k,2)+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=comb(k,2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n,r):
  return factorial(n)//factorial(n-r)//factorial(r)
S=input()
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(1,N+1): 
  s+=int(S[-i])*(10**(i-1))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=comb(k,2)+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=comb(k,2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb
S=input()
N=len(S)
mod=[0 for i in range(2019)]
for i in range(N):
  s=S[i:N+1]
  mod2=int(s)%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=comb(k,2)+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=comb(k,2)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n,r):
  return factorial(n)//factorial(n-r)//factorial(r)
S=input()
N=len(S)
mod=[0 for i in range(2019)]
for i in range(N):
  s=S[i:N+1]
  mod2=int(s)%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=comb(k,2)+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=comb(k,2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s = input()

remainder = defaultdict(int)
res = 0
for c in s:
    new_remainder = defaultdict(int)
    for r_val, r_cnt in remainder.items():
        y = (r_val * 10 + int(c)) % 2019
        new_remainder[y] += r_cnt
    new_remainder[int(c)] += 1
    res += new_remainder[0]
    remainder = new_remainder

print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()

count = 0
for i in range(len(S)-2):
    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:
S = input()

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

print(count)