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:
from collections import deque
s=input()
ans=0
a=[sum([1 for i in range(len(s)-3-j) if int(s[i:i+4+j])%2019==0]) for j in range(len(s)-3)]
print(sum(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
s = len(S)
ans = 0

for i in range(s - 4):
    for j in range(i+4, s+1):
        k = int(S[i:j])
        if k % 2019 == 0:
            ans += 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
l = []
for i in range(1, 100000):
    l.append(str(2019*i))

s = input()
ans = dict()
for i in l:
    if i in s:
        for j in range(len(s)-len(i)+1):
            if s[j:j+len(i)] == i:
                ans[str(j+1)+"-"+str(j+len(i))] = 1

# print(l)
print(len(ans))
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
cnt = 0
iend = l-3
jend = l+1

for i in range(iend):
    s2 = s[i:]
    for j in range(i+4, jend):

        x = int(''.join(s2[:j]))
        if x < 2019: continue
        if x % 2019 == 0: cnt+= 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = input()
lenN = len(N)
cnt = 0
for i in range(0,lenN-3):
  if i > 200000:
    break
  for j in range(i + 3,lenN + 1):
    if j > 200000:
      break
    p = int(N[i:j])
    if p % 2019 == 0:
      cnt += 1


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
for i in range(len(s)-2):
    for j in range(i+4,len(s)+1):
        x = s[i:j]
        x = int(x)
        if(x % 2019 == 0):
            ans += 1
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
s = input()
b=int(s)
a = [int(c) for c in s]
total=0
for i in range(0,len(a)-2):
  for j in range(i+4,len(a)+1):
    d=int(s[i:j])
    if d%2019==0:
      total+=1
print(total)

Submission status: Time Limit Exceeded

Solution code:
from math import log10

def f(s):
    ans = 0
    while s > 2019:
        if s % 2019 == 0:
            ans += 1
        s //= 10
    return ans

s = int(input().strip())
n = int(log10(s)) + 1
ans = 0

while s > 2019:
    ans += f(s)
    n -= 1
    s %= (10**n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = 2019
dp = [0]*(len(s)+5)

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

dpa = [0]*(2019)

for i in range(len(s)+1):
    v = dp[i]
    dpa[v] += 1

ans = 0
for i in range(len(dpa)):
    ans += dpa[i] * (dpa[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#d
N = str(input())

def fun(a,b):
    ans=0
    for x in range(len(a)-b+1):
        if int(a[x:x+b])%2019==0:
            ans+=1
    return ans

if len(N)<4:
    print(0)
else:
    ans=0
    for x in range(3,len(N)+1):
        ans+=fun(N,x)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
i = 0
j = 4
count = 0
if len(S) < 4:
    print(0)
    exit()
while True:
    if int(S[i:j]) % 2019 == 0:
        count += 1
    j += 1
    if j == len(S) + 1:
        if i == len(S) - 3:
            break
        else:
            j = i + 4
            i += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
count = 0
for n in range(4,len(S)+1):
    for i in range(len(S)-n+1):
        new = S[i:i+n]
        if int(''.join(new)) % 2019 ==0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def multiples(S):
  n = len(S)
  c = 0
  for i in range(n):
    for j in range(i+1,n+1):
      num = int(S[i:j])
      if num%2019==0:
        c+=1
  print(c)

if __name__=='__main__':
  S = input()
  multiples(S)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0

for n in range(3, len(S)):
    for i in range(len(S)-n):
        ans += 1 if int(S[i:i+n+1]) % 2019 == 0 else 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
ans = 0
try:
    for i in range(n):
        for j in range(i+1, n+1):
            if len(s[i:j]) >= 4:
                if int(s[i:j])%2019 == 0 :
                    ans += 1
except:pass

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
sl = len(s)
num = str()
n = 0
ans = 0

for i in range(0,sl-3):
    for j in range(i+3,sl+1):
        num = s[i:j]
        n = int(num)
        if n%2019 == 0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

def aaa(s, num):
    x = 0
    for i in range(4,num+1):
        for j in range(num - i + 1):
            if int(s[j:j+i]) % 2019 == 0:
                x += 1
    print(x)

aaa(s,num)

Submission status: Time Limit Exceeded

Solution code:
def Sol(st):
    n = len(st)
    count = 0
    for i in range(n):
        for j in range(i+3,n):
            if int(st[i:j+1])%2019 == 0:
                count += 1

    print(count)
    return

    

#for t in range(int(input())):
#n,k,c,d = map(int,input().split())
n = input()
#arr = []
#for i in range(n):
#    arr.append(input())
#arr = list(map(int,input().split()))
#k = input()
#n = int(input())
Sol(n)

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):
    if int(S[i:j]) % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
ans=0
for i in range(0,n-3):
    for j in range(i+4,n+1):
        s3=sum(list(map(int, s[i:j])))
        if ((s3 % 3) == 0):
            kazu = int(s[i:j])
#            print (s3, kazu)
            if ((kazu % 2019) == 0): ans = ans+1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
ans = 0

for i in range(len(S)+1):
    for j in range(i+1,len(S)+1):
        K = S[i:j]
        L = [int(s) for s in K]
        T = len(L)
        n = 0
        for k in range(T):
            n = n + L[k]*(10**(len(L)-k-1))
            k = k + 1
        if n % 2019 == 0:
            ans += 1
        j = j + 1
    i = i + 1
        

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.exit()
#sorted( ,reverse=True)
S = str(input())
#S,T = map(int, input().split())
#A = list(map(int, input().split()))
#print(N)
#print(S,T)
#print(A)
ans = 0
for i in range(len(S)-3):
    s = int(S[i:])
    #print(s)
    while s > 2018:
        #print(s)
        if int(s) % 2019 == 0:
            ans += 1
        s = s // 10
        
        #print(S[i:j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=2019
cnt=0
for i in range(len(s)-1):
    for j in range(i+1,len(s)+1):
        ss=s[i:j]
        #print(float(ss))
        if int(ss)%n==0:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations

s = input()

a = np.append(0, np.cumsum(np.array(list(s), dtype=np.int64))%3)
x = np.where(a==0)[0].tolist()
y = np.where(a==1)[0].tolist()
z = np.where(a==2)[0].tolist()

ans = 0
for i,j in combinations(x,2):
    if i+3 > j:
        continue
    if eval(s[i:j] + " % 2019") == 0:
            ans += 1
for i,j in combinations(y,2):
    if i+3 > j:
        continue
    if eval(s[i:j] + " % 2019") == 0:
            ans += 1
for i,j in combinations(z,2):
    if i+3 > j:
        continue
    if eval(s[i:j] + " % 2019") == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

S = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)
import heapq #優先度付きqueue


a = [0]
heapq.heapify(a)  # aを優先度付きキューに

for i in range(0,ls):
    heapq.heappush(a,(S%10**(i+1))%2019)
#print(a)

cur=-1
count=1
ans=0

while len(a)>0:
    c=heapq.heappop(a)
    #print(c)
    if cur==-1:
        cur=c
    elif cur==c:count+=1
    else: 
        ans+=count*(count-1)//2
        count=1
        cur=c
print(ans)

# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
length = len(S)
count = 0
ans = 0

for i in range(length):
    res = 0
    for j in range(i, length):
        res = (res * 10 + int(S[j])) % 2019
        if res == 0:
            count += 1
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import collections
    def input():
        return sys.stdin.readline()[:-1]
    S=input()
    result=0
    for i in range(len(S)-3):
        k=i
        for j in range(i+4,len(S)+1):            
            a=S[k:j]
            if int(a)%2019==0:
                result+=1
                k+=j-k
                b=S[k:j]
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
line = input()
size = len(line)
num = [int(x) for x in list(str(line))]
i = 0
count = 0
if int(line)==2019:
    print("1")
else:
    while i<size-4:
        j = i + 4
        while j<=size:
            x = num[i:j]
            s = ""
            for k in range(len(x)):
                s = s + str(x[k])
            if int(s)%2019 == 0:
                count = count+1
                j = j + 3
            j = j + 1
        i = i + 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout  
  
def main(): 
	strInput = stdin.readline().rstrip()
	lenn = len(strInput)
	cnt  = 0
	cache = set()
	if len(strInput) < 4:
		for y in strInput:
			if y == '0':
				cnt+=1 
		stdout.write( str(cnt)+'\n')
	else:
		for i in range(0, lenn - 3):
			for k in range(i + 4, lenn + 1):
				#print("combination", strInput[i: k] )
				comb = strInput[i: k]
				if comb in cache:
					cnt+=1
				elif int(comb) % 2019 == 0 :	
						cnt+=1
						cache.add(comb)
						#print(strInput[i: lenn])
			if strInput[i] == '0':
				cnt+=1	
		for j in range(lenn - 3, lenn):
			if strInput[j] == '0':
				cnt+=1	
		stdout.write( str(cnt)+'\n')
if __name__ == "__main__": 
	main()

Submission status: Time Limit Exceeded

Solution code:
i = list(input())
pattern = int((len(i) * (len(i) + 1)) / 2)
count = 0
a, b = 0, 0
for j in range(pattern):
    if int("".join(map(str, i[a: b + 1]))) % 2019 == 0 and int("".join(map(str, i[a: b + 1]))) != 0:
        count += 1
    if b == len(i) - 1 and a == len(i) - 1:  # 調べきったら 
        break
    elif b == len(i) - 1:
        a += 1
        b = a + 3  # 4桁未満は調べても意味ない
    else:
        b += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import re
from collections import namedtuple
match = namedtuple('match', 'start,end')


s = input()

# パターンを収集
pats = []
s_set = set()
for i in range(1, 10001):
    s_set.add(str(2019*i).rstrip('0'))
for _s in s_set:
    pats.append(re.compile('(?=({})(0*))'.format(_s)))

# マッチを取る
m_set = set()
count = 0
for pat in pats:
    read_set = set()
    for m in re.finditer(pat, s):
        g = m.group
        m_set.add(match(m.start(), m.start()+len(g(1))))
matches = sorted(m_set, key=lambda m: m.start)

# ペアを集計
pairs = []
for i, m in enumerate(matches):
    ind = i + 1
    while (ind<len(matches)) and (m.end >= matches[ind].start):
        ind += 1
    if ind<len(matches):
        _m = matches[ind]
        inter = list(set(s[m.end:_m.start]))
        if inter[0]=='0' and len(inter)==1:
            pairs.append((m, _m))

# 最終的な値を算出
def get_comb(n):
    return n*(n-1)//2

pairs = sorted(pairs, key=lambda p: p[0].start)
ms = []
current_num = 1
res = len(matches)
for i in range(len(pairs)):
    if i+1<len(pairs) and pairs[i][1] == pairs[i+1][0]:
        current_num += 1
    else:
        res += get_comb(current_num)
        current_num = 1

print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S = input()

"""
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) % 2019] += v

    counts = nextCounts
    total += counts[0]
    #print(counts)

print(total)

"""

"""
def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:

        # q is quotient
        q = a // m

        t = m

        # m is remainder now, process
        # same as Euclid's algo
        m = a % m
        a = t
        t = y

        # Update x and y
        y = x - q * y
        x = t

    # Make x positive
    if x < 0:
        x = x + m0

    return x
"""


#div10 = modInverse(10, 2019)

div10 = 202
#m = 1
mInv = 1

off = 0
counts = Counter()
total = 0
for d in S:
    d = int(d)
    off = 10 * off + d
    #m *= 10
    mInv = (mInv * div10) % 2019
    #assert modInverse(m, 2019) == mInv
    counts[((d - off) * mInv) % 2019] += 1
    total += counts[((0 - off) * mInv) % 2019]

print(total)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
if N < 4:
    print(0)
elif N == 4:
    ans = 0 + 1*(int(S)%2019 == 0)
    print(ans)
    
else:
    ans = 0
    for n1 in range(N-3):
        for n2 in range(n1+4, N+1):
            num = S[n1:n2]
            L = len(num)
            temp = 0
            temp2 = int(num)
            if not temp2 == 0:
                for l in range(L):
                    temp += int(num[l])

                #if temp%3 == 0:
                #    temp2 = int(num)//3
                    
                if temp2%2019 == 0:
                    ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
s=input()
n=len(s)
if n<=4:
  print(0)
  sys.exit()  
p=2019
cnt=0
for i in range(n-3):
  S=s[i:i+3]
  for j in range(i+3,n):
    S+=s[j]
    if int(S)%2019==0:
      cnt+=1
      break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
v = []
for i in s:
    v.append(int(i)%3)
#print(v)
c = 0
for i in range(0,l-4):
    kari = sum(v[i:i+4])
    #print(kari)
    for j in range(i+4,l):
        kari += v[j]
        """
        u = v[j]
        if kari == 0:
            kari += u
        elif kari == 1:
            if u == 2:
                kari = 0
            else:
                kari += u
        else:
            if u == 1:
                kari = 0
            elif u == 2:
                kari = 1
                """
        if kari%3==0:
            tmp = int(s[i:j+1])
            if tmp%2019 == 0:
                c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    s = S()
    n = len(s)
    # c=0
    # for i in range(n):
    #     for j in range(i+3,n):
    #         x = s[i:j+1]
    #         z = int(x)
    #         if z>=2019:
    #             if int(x)%2019==0:
    #                 c+=1
    # print(c)
    numMultiples = 0
    seenRemainders = [set() for i in range(n)]
    for i in range(n):
        remainder = 0
        prefixesFound = 0
        for j in range(i,n):
            z=10 * remainder + int(s[j])
            remainder = (10 * remainder + int(s[j])) % 2019
            if remainder in seenRemainders[j]:
                break
            seenRemainders[j].add(remainder)
            if remainder == 0:
                prefixesFound+=1
        numMultiples += (prefixesFound * (prefixesFound + 1))// 2
    print(numMultiples)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
l=len(S)
z=0
for x in range(l):
    for y in range(l-x-3):
        T=S[x:x+y+4]
        t=int(T)
        
        if t%3==0:
            if t%673==0:
                z+=1
            
print(z)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
for i in range(len(s)):
    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()
count=0
for i in range(len(s)-3):
    for j in range(i+3,len(s)):
        num=int(s[i:j+1])
        if num%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:

S = int(input())
rui = [0] * 2019
for i in range(2 * 10 ** 5 + 1):
    rui[((S % (10 ** i)) % 2019)] += 1

ans = 0
#for i in rui:
#    if i >= 2:
#        ans += (i * (i - 1) // 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()
MOD = 2019
le = len(s)
ans = 0
for i in range(le - 1):
    for j in range(i + 1, le + 1):
        if int(s[i:j]) % MOD == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
n = len(s)

ans = 0
digit_sum_mod3 = 0
start = 0

while start <= n-4:
  end = start + 4
  while end <= n:
    if end == start + 4:
      for i in range(4):
        index = start + i
        digit_sum_mod3 += int(s[index])
        digit_sum_mod3 %= 3
    if digit_sum_mod3 == 0:
      if int(s[start:end]) % 2019 == 0:
        ans += 1
    if end != n:
      digit_sum_mod3 += (int(s[end]) % 3)
      digit_sum_mod3 %= 3
    end += 1
  digit_sum_mod3 = 0
  start += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
ans = 0
for i in range(0,len(s)+1):
    for j in range(i + 1, len(s)+1):
        if int(s[i:j]) % 2019 == 0:
            ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
if N<4:
  print(0)
  exit(0)
M=2019
X=S
ans=0
x=[]
for l in range(N-3):
  for r in range(l+3,N):
    if int(X[l:r+1])%M==0:
      ans+=1
      x.append([l,r])
      break
def search(a,x,j):
  while j<len(x):
    if a[1]+1==x[j][0]:
      return 1+search(x[j],x,j+1)
    j+=1
  return 0
for i,a in enumerate(x):
  ans+=search(a,x,i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0]
    for i in range(len(S)):
        mod_all_bit.append(int_S % (10**(i+1)) % 2019)
    couter = {}
    for key in mod_all_bit:
        couter[key] = 0
    for key in mod_all_bit:
        couter[key] += 1
    ans = 0
    for key, val in couter.items():
        if val >= 2:
            ans += int(val * (val-1) * 0.5)
    return ans


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)

Submission status: Time Limit Exceeded

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

numMultiples = 0
seenRemainders = [set() for _ in range(n)]

for i in range(n):
    remainder = 0
    prefixesFound = 0

    for j in range(i, n):
        remainder = (10 * remainder + int(s[j])) % k

        if remainder in seenRemainders[j]:
            break

        seenRemainders[j].add(remainder)

        if remainder == 0:
            prefixesFound += 1

    numMultiples += prefixesFound * (prefixesFound + 1) // 2

print(numMultiples)

Submission status: Time Limit Exceeded

Solution code:

def main():
    S = input()
    cnt = 0

    #d = []
    #for i in range(2019, 10**20000):
    #    if i % 2019 == 0:
    #        d.append(str(i))
    
    #print(d)

    if len(S) < 4:
        return 0
    
    #for i in d:
    #    cnt += S.count(i)
    memo = {}

    for i in range(0, len(S)-3):
        c = 0
        for j in range(4, len(S)-i+1):
            num = int(S[i:i+j])
            #print(num)
            if num in memo:
                cnt += memo[num]
                break
            if num % 2019 == 0:
                c += 1
                cnt += 1
                memo[num] = c
        
    return cnt
    

if __name__ == '__main__':
    cnt = main()
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
answer = 0
for i in range(1,int(s)//2019):
  if str(2019*i) in s:
    answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
s=input()
slen=len(s)
count=0
skip=0
ri=slen-4
for i in range(ri):
  rj=i+4
  for j in range(rj,slen):
    if skip != 0:
      skip+=1
      skip%=5
      continue
    targ=int(s[i:j+1])
    if targ%2019==0:
      count+=1
      skip+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S=input()
ans = 0
for i in range(len(S)-4):
    k=5
    while k-(len(S)-i) < 1:
        if int(S[i:i+k]) % 2019 != 0:
            k+=1
        else:
            ans +=1
            k+= len(S[i:i+k])-2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
x=list(s)
y=[int(i) for i in x]
ans=0
for i in range(len(s)-3):
  for j in range(i+4,len(s)+1):
    if sum(y[i:j])%3==0:
      t=int(s[i:j])
      if t%673==0:
        ans=ans+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

n = int(input())  # nは入力回数
l = [int(x) for x in list(str(n))]

num=len(l)
count=0

for i in range(num): 
    for j in range(num):
        if i>=j or j-i<3:
            pass
        else:
            new_n = int(reduce(lambda x, y: x + y, [str(x) for x in l[i:j+1]]))
            if new_n%2019==0:
              count=count+1  
print(count)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = len(a)
d = 4
counter = 0
while d <= b:
    e = 0
    while e + d <= b:
        t = int(a[e: e + d])
        if t % 2019 == 0:
            counter += 1
        e = e + 1
    d = d + 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline

    s = str(input().rstrip())
    num = ""
    li = []
    f = 0
    mi = 0
    li_append = li.append

    cm = {}
    def cmb(n):
        if n in cm:
            return cm[n]
        else:
            a = n * (n - 1) // 2
            cm[n] = a
            return a



    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li_append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            mi += cmb(f+1)
            f = 0

    co = Counter(li)
    val = [i for i in co.values() if i > 1]
    ans_1 = 0

    for x in val:
        ans_1 += cmb(x)
    ans2 = 0
    if 0 in co:
        ans2 = co[0]
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = []
for y in range(4, len(s)+1) :
    for x in range(0, len(s)) :
        a = int(s[x:x+y])
        if a % 2019 == 0:
            ans.append(a)
        if x+y == len(s):
            break
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  list_n = list(str(n))
  count = 0
  for i in range(len(list_n)):
    for j in range(i+4, len(list_n)+1): 
      if int(''.join(list_n[i:j])) % 2019 == 0:
        count += 1    
  print(count)
main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
N=[0]*2020
x=0
for i in reversed(range(n)):
    x+=int(s[i])*(10**(n-i-1))
    x%=2019
    N[x%2019]+=1
ans=N[0]
for j in N:
    ans+=j*(j-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

s = input().rstrip()
n = len(s)
ranges = []
g = [[] for _ in range(n + 1)]
ans = 0

for i in range(n):
    for j in range(i + 3, i + 10**6):
        if j >= n:
            continue
        s_ = s[i:j + 1]
        if int(s_) % 2019 == 0:
            ranges.append([i, j + 1])
            g[i].append(j + 1)

visited = set()
ans = 0

for i in range(n):
    if i in visited or len(g[i]) == 0:
        continue
    visited.add(i)
    d = 1
    while True:
        i = g[i][0]
        if len(g[i]) == 0:
            ans += (1 + d) * d // 2
            break
        else:
            d += 1
            visited.add(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=list(map(int,list(input())))
N=len(S)

remainder=[0]*2019
s=[0]*N
for i in range(1,N+1):
  s[i-1]=S[-i]*(10**(i-1))

val=0
for i in range(N):
  val+=s[i]
  remainder[val%2019]+=1

ans=remainder[0]
for i in range(2019):
  if remainder[i]<=1:
    continue
  else:
    ans+=remainder[i]*(remainder[i]-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
p=set()
ans=0
for c in s:
    ci=int(c)
    t=set()
    for i in p:
        i=(i*10+ci)%2019
        if i==0:
            ans+=1
        else:
            t.add(i)
    t.add(ci)
    p=t.copy()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
n = len(s)

ans = 0
digit_sum_mod3 = 0
start = 0

for i in range(n-3):
  if start <= n-4:
    end = start + 4
    while end <= n:
      if end == start + 4:
        for k in range(4):
          index = start + k
          digit_sum_mod3 += int(s[index])
          digit_sum_mod3 %= 3
      if digit_sum_mod3 == 0:
        if int(s[start:end]) % 2019 == 0:
          ans += 1
      if end != n:
        digit_sum_mod3 += (int(s[end]) % 3)
        digit_sum_mod3 %= 3
      end += 1
    digit_sum_mod3 = 0
    start += 1

print(ans)

Submission status: Time Limit Exceeded

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

if l < 4:
    print(0)
    exit()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
result = 0
s = input()
slen = len(s)
i = 1
while i < slen:
    limit = slen-i
    p = 0
    seisuu = ""
    while p <= limit:
        seisuu += (s[i+p-1])
        p += 1
        if int(seisuu) % 2019 == 0:
            result += 1
    i += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
s1=input()
s=int(s1)

keta=4
count=0
while keta<=len(s1):
    for i in range(0,len(s1)-keta+2):
        if int(s1[i:i+keta-1])%2019==0:
            count+=1
    keta+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
bS = input()
S = list(map(int, bS))
ls = len(S)
c = 0
for s in range(ls - 3):
    n = sum(S[s:s+3])
    if S[s] == 0:
        continue
    for e in range(s + 3, ls):
        n += S[e]
        if e - s == 3 and S[s] == 1:
            continue
        if n % 3 == 0 and int(bS[s:e+1]) % 673 == 0:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:

S = str(input())

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

print(count)