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(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    S = input()
    d = [0]*2019
    dn = [0]*2019
    ans = 0
    for s in S:
        sn = int(s)
        dn[sn] += 1
        for i in range(2019):
            dn[(i*10+sn)%2019] += d[i]
        d, dn = dn, d
        for i in range(2019):
            dn[i] = 0
        ans += d[0]
    print(ans)






main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
r = len(s)
c = 0
for i in range(r+1):
  for j in range(i+1,r+1):
    d = int(s[i:j])
    if d%2019==0:
      c += 1
    else:
      pass
print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N = input()
    l = len(N)
    listt = range(l)
    pl = list(itertools.combinations(listt, 2))
    k = 0
    for i in pl:
        fig = N[i[0]:i[1]+1]
        if (int(fig)%2019)==0:
            k = k + 1
    print(k)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

S = int(input())
l = [int(s) for s in list(str(S))]
ans = 0

for i in range(len(l)):
    for j in range(i+1, len(l)+1):
        if j - i <=3:
            continue
        new = int(reduce(lambda x, y: x + y, [str(x) for x in l[i:j]]))
        if new % 2019 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
b=0
m=len(s)
c=0
for i in range(m-1,2,-1):
    a=s[i-2]+s[i-1]+s[i]
    for j in range(i-3,-1,-1):
        # if c==1 and int(s[j])%3!=0:
        #     c=0
        #     continue
        a=str(a)
        a=int(s[j]+a)
        # print(a)
        # c=0
        # if a%3!=0:
        #     continue
        # c=1
        if a%2019==0:
            # print(b)
            b+=1
            break

print(b)

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)):

        x = int(S[i:j+1])
        

        if x % 2019 == 0:
            #print(S[i:j+1])
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
s_len = len(s)
count = 0

for i in range(s_len-4):
    for j in list(range(i+4, s_len)):
        s_s = int(s[i:j+1])

        if s_s % 2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

@lru_cache()
def pow(i):
    if i==0:
        return 1
    elif i==1:
        return 10

    if i%2==0:
        return pow(i//2)*pow(i//2)
    else:
        return pow(i-1)*10

S=input()
count=[0 for i in range(2019)]
length=len(S)
S=int(S)

for i in range(length+1):
    n=S%pow(i)
    count[n%2019]+=1



retval=0
for key in range(2019):
    retval+=count[key]*(count[key]-1)//2


print(retval)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[-1 for i in range(len(S))] for j in range(len(S))]
 
ans = 0
 
for i in range(len(S)):
    for j in range(len(S)):
        if dp[i][j]!=-1:
            continue
        else:
            if j<i+4:
                dp[i][j]=0
            else:
                num = int(S[i:j+1])
                if num%2019==0:
                    dp[i][j]=1
                    ans+=1
                    for w in range(-4,5):
                        if j+w>=0 and j+w<len(S):
                            dp[i][j+w]=0
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product

# import numpy as np

# sys.setrecursionlimit(10**5 + 1)
input = sys.stdin.readline
write = sys.stdout.write

# MOD = 10**9 + 7
MOD = 998244353


if __name__ == "__main__":

    s = input().strip()
    cur = {0: 0}
    mod = 2019
    ans = 0
    for ch in s:
        d = int(ch)
        nxt = defaultdict(int)

        for remain in cur:
            cnt = cur[remain]
            remain = (remain*10 + d) % mod
            if not remain:
                cnt += 1
                ans += cnt
            nxt[remain] += cnt

        nxt[d] += 0
        cur = nxt

    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

digits = [ord(c) - ord('0') for c in s]

total = 0
for i in range(n):
    if digits[i] == 0:
        continue

    num = 0
    for j in range(i, n):
        num = num * 10 + digits[j]
        if j + 4 < i:
            continue

        if num % 2019 == 0:
            total += 1

print(total)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = input() #1行目のNを取得する
l = len(n)
count = 0
list=[]
for i in range(l-3):
  for j in range(i+4,l+1):
    if int(n[i:j]) >= 2019:
      if int(n[i:j]) % 2019 == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mods = [0 for i in range(2019)]
mods[0] = 1
res = 0

for i in range(n - 1, -1, -1):
    ss = int(s[i:])
    curr = ss % 2019
    res += mods[curr]
    mods[curr] += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
s=[int(x) for x in list(str(input()))]
ans=0
for i in range(1,len(s)+1):
    for j in range(i+2,len(s)+1):
        figure=0
        if(sum(s[-i:-j-1:-1])%3==0):
            for k in range(j-i+1):
                figure+=s[-(i+k)]*10**k
            if(figure%673==0):
                ans+=1
                i+=3
                continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
table={}
cnt=0
for i in range(1,10*6):
    table[str(2019*i)]="OK"
for i in range(2*10**5):
    for j in range(i+3,2*10**5):
        if j>=len(s):
            break
        if "".join(s[i:j+1]) in table:
            cnt+=1


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=input()
num=0
res=0
if int(S)<2019:
    res =0
else:
    for i in range(len(S)-1):
        for n in range(i+1,len(S)+1):
            num=int(S[i:n])
            if num%2019==0:
                res = res+1
print(res)

Submission status: Time Limit Exceeded

Solution code:
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
            continue
        else:
            continue
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def f(s, i, j):
    return reduce(lambda x,y: x*10+y, s[i:j+1])

s = [int(i) for i in list(input().strip())]
n = len(s)
ans = 0

for i in range(n-3):
    for j in range(i+3,n):
        x = f(s, i, j)
        if x == 0:
            continue
        if x % 2019 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
r = 0
n = len(s)
for i in range(n):
    for k in range(i + 3, n + 1):
        if i + 3 <= n:
            if int(s[i:k]) % 2019 == 0:
                r += 1
print(r)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

simo4 = set()
for i in range(1,100001):
    s = str(2019*i)
    if '0' not in s:
        simo4.add(s[-4]+s[-3]+s[-2]+s[-1])

l = len(S)
ans = 0
for i in range(l-1,2,-1):
    tmp = S[i-3]+S[i-2]+S[i-1]+S[i]
    if tmp not in simo4:
        continue
    else:
        if int(tmp)%2019 == 0:
            ans += 1
        for j in range(i-4,-1,-1):
            tmp = S[j]+tmp
            if int(tmp)%2019 == 0:
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
line = input()
num = [int(x) for x in list(str(line))]
i = 0
count = 0
while i<len(line)-4:
    j = i + 4
    while j<=len(line):
        x = num[i:j]
        s =int(reduce(lambda a, b: a + b, [str(a) for a in x]))
        if int(s)%2019 == 0:
            count = count+1
        j = j + 1
    i = i + 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import math
import bisect

debug = False

def log(text):
    if debug:
        print(text)


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    
    s = lines[0]
    return (s, )


def solve(s, ):

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


    return count

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    s_set = set()
    s_len = len(s)
    for i in range(s_len-3):
        for j in range(i+4, s_len+1):
            if int(s[i:j])%3 == 0: 
            	if int(s[i:j])%673 == 0:
              		s_set.add((i, j))

    return len(s_set)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    a = "".join(["".join(["1"for j in range(i-4) if int(s[j:i])%2019==0]) for i in range(len(s)+1)])
    print(len(a))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
problemInput = input()
count = 0

if len(problemInput) > 3:
    for i in range(3, len(problemInput)):
        for j in range(0, i - 2):
            temp_str = problemInput[j: i + 1]
            tempNum = int(temp_str)

            if tempNum % 2019 == 0:
                count += 1

print(count)

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

Submission status: Time Limit Exceeded

Solution code:
import re

s = input('')
max_s = int(200000)
rec = 0
for m in (range(max_s+1)):
    ms=str(2019*m)
    for i in range(len(s)):
        rec+=s.count(ms,i,i+len(str(ms)))
print(rec)

Submission status: Time Limit Exceeded

Solution code:
S = input()

count = 0
for num_length in range(4, len(S) + 1):
    for i in range(len(S) - num_length + 1):
        j = i + num_length - 1
        sub_S = int(S[i:j + 1])
        if sub_S % 2019 == 0:
            count += 1
# for times in range(1, 101):
#     num = 2019 * times
#     if num > int(S): break
#     num_length = len(str(num))
#     for i in range(len(S) - num_length + 1):
#         j = i + num_length - 1
#         sub_S = int(S[i:j + 1])
#         if num == sub_S:
#             count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

rem = {}
rem[0] = 1

moji = ''
MOD = 2019
cnt = 0

for i in range(1, len(S) + 1):
    moji = S[-i:]
    r = int(moji) % 2019
    if r in rem:
        cnt += rem[r]

    if r not in rem:
        rem[r] = 1
    else:
        rem[r] += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
ans=0
N=len(S)
for i in range(N):
    for j in range(i+4,N+1):
        # print(S[i:j])
        tmp=int(S[i:i+j])
        if tmp%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
cnt=0
for n in range(len(s)):
    for m in range(len(s)+1):
        if s[n:m]!="":
            if int(s[n:m])%2019==0:
                cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li.append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            if f > 0:
                mi += ((f + 1) * f) // 2
                f = 0

    co = Counter(li)
    val = co.values()
    ans_1 = 0

    for i in val:
        if i > 1:
            ans_1 += (i * (i - 1)) // 2
        else:
            continue
    ans2 = 0
    if 0 in co:
        zero = co[0]
        ans2 = zero
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import Counter
import itertools
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################

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

Submission status: Time Limit Exceeded

Solution code:
def n_gram(target,n):
    a = (int(target[idx:idx + n]) for idx in range(len(target) - n + 1))
    return tuple(a)

count = 0
s = input()
n = 4
num_list = ()
s_len = len(s)
while n <= s_len:
    num_list = num_list + n_gram(s,n)
    n += 1
for num in num_list:
    if num % 2019 == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
L = len(s) if len(s) <= 200000 else 200000

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
res = 0

for i in range(3, len(S)):
  last = S[i]
  for j in range(i-3):
    product = int(S[j:i+1])

    if product % 2019 == 0:
      res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:

def find_list(arr,n):
	nummultiples=0
	seenRemainders=[0]*n
	for i in range(n):
		remainder=0
		prefixesFound=0
		for j in range(i-1,n):
			remainder=(10*remainder+int(arr[j]))%2019
			if seenRemainders[j] ==remainder:
				break
			seenRemainders[j]=remainder
			if remainder==0:
				prefixesFound+=1
				
		nummultiples+=prefixesFound*(prefixesFound+1)//2
		
	return nummultiples
	
s=list(input())
print(find_list(s,len(s)))

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
len = len(S)
counter = 0
for x in range(3,len):
    for i in range(0, len - x):
        value = S[i:x + i + 1]
        if int(value) % 2019 == 0:
            counter = counter + 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = str(input())

#N = str(14282668646)

count = 0
lenN = len(N)+1
for i in range(0, lenN):
    for j in range(i+4, lenN):
#        print (i, j)
        number = int(N[i:j])
        if number%2019 == 0:
            count +=1
            break
#            print (i, j)
#T = int(N)//2019
#
#for t in range (T):
#    den = 2019*t
#    length = len(str(den))
#    sum_length = len(N)
#    for i in range(sum_length-length):
#        if den == int(N[i:i+length]):
#            count +=1

print (count)

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

base_nums = [2019 * i for i in range(1, min(10**4, int(s)))]

memo = {}
def find_num(s):
    if s in memo:
        return memo[s]
    total = 0
    for num in base_nums:
        splitted = s.split(str(num))
        for i in range(1, len(splitted)):
            total += 1 + find_num(str(num).join(splitted[i:]))
    memo[s] = total
    return total
print((find_num(s)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = []
for i in range(len(S)):
    for j in range(i+3, len(S)):
        int_join_A = int(''.join(S[i:j+1]))
        if int_join_A % 2019 == 0:
            ans.extend((i, j))
print(len(ans) // 2)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
numMultiples=0
S=input()
N=len(S)
seenRemainders=[set()]*(N+1)
for i in range(N):
    remainder = 0
    prefixesFound = 0
    for j in range(i,N):
        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(int(numMultiples))

Submission status: Time Limit Exceeded

Solution code:

S = str(input())

n = len(S)

cnt = 0
for i in range(n+1):
    for j in range(i+1, n+1):
        s = S[i:j]

        if int(s) % 2019 == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input();

ans = 0;

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(1, 10**5):
    num = str(2019*i)
    if num in s:
        for j in range(len(s)-len(num)+1):
            if num == s[j:j+len(num)]:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combinations_count(n):
  return n*(n-1)//2
s = input()
l = len(s)
lis = []
for i in reversed(range(l)):
  k = int(s[i:l])
  lis.append(k%2019)
lis.append(0)
lis.sort()
ll = len(lis)
ans = 0
tem = 1
for i in range(1, ll):
  if lis[i-1] == lis[i]:
    tem += 1
  elif tem >= 2:
    ans += combinations_count(tem)
    tem = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

cnt = 0

for i in range(4,len(S)):
    for j in range(len(S)):
        if j+i <= len(S):
            tmp = S[j:j+i]
            if int(tmp) % 2019 == 0:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
L = len(S)
N = 0

for i in range(L - 3):
    for j in range(4,L - i+1):
        P = S[i:i + j]
        if int(P) % 2019 == 0: N += 1

print(N)

Submission status: Time Limit Exceeded

Solution code:
S=input()
SS=[a for a in S]
N=len(SS)
answer=0
for a in range(N):
    for b in range(a,N):
        z=SS[a:b+1]
        Y=int(''.join(z))
        if Y%2019==0:
            answer+=1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
ok = 0
test = str()

for i in range(1, len(S) + 2):
    for j in range(i, len(S) + 2):
        test = "".join((S[i - 1:j - 1]))
        if len(test) != 0:
            test = int(test)
            if test % 2019 == 0:
                ok += 1

print(ok)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
follow = 0
for i in range(N):
  Amari_ = (int(S[N-i-1]) * pow(10, i) + follow) % 2019
  ans += amari[Amari_]
  amari[Amari_] += 1
  follow = Amari_
ans += amari[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    s = input()
    dp = {}
    dp[0] = 0
    ans = 0
    calc = [ [(i + j * 10)% 2019 for j in range(10000)] for i in range(10)]
    for c in s:
        if 0 not in dp:
            dp[0] = 0
        dp[0] += 1
        cc = int(c)
        dp = {calc[cc][k]: v for k,v in dp.items()}
        if 0 in dp:
            ans += dp[0]
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
count=0
if n<4:
    print(0)
else:
    for i in reversed(range(2,n)):
        k=int(s[i-2:i+1])
        h=3
        for j in reversed(range(0,i-2)):
            k=k+(10**(h)%2019)*int(s[j])
            h+=1
            if k%2019==0:
                count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import re


def main(S=None):
    if not S:
        S = input()
    count = 0
    s_len = len(S)
    for candidate_len in range(4, s_len+1):
        for i in range(s_len):
            if i+candidate_len > s_len:
                break
            if int(S[i:i+candidate_len]) % 2019 == 0:
                count += 1
    print(count)


if __name__ == "__main__":
    # main("1817181712114")
    # main("14282668646")
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from math import ceil

def main():
    string = stdin.readline()

    new_string = ""
    for char in string:
        if char in "123456789":
            new_string += char

    count = 0

    pos_start = 0
    for start in new_string:
        pos_end = pos_start + 4
        for end in new_string[pos_start+3:]:
            if (int(new_string[pos_start:pos_end]) % 2019) == 0:
                count += 1 
            pos_end += 1
        pos_start += 1

    print(count)

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def slove(n):
    count = 0
    num = len(n)+1
    dp = {}
    for i in range(num-4):
        for j in range(i+1, num):
            tmp = int(n[i:j])
            if tmp in dp and dp[tmp]:
                count+=1
            else:
                if tmp % 2019 == 0:
                    count += 1
                    dp[tmp] = True

    return count

if __name__ == "__main__":
    n = input()
    print(slove(n))

Submission status: Time Limit Exceeded

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

print(a)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

Submission status: Time Limit Exceeded

Solution code:
N = input()
D = len(N)
answer = 0
if D >3 :
    for i in range(D-3):
        for k in range(D-3-i):
            if int(N[i:D-k]) % 2019 ==0:
                answer +=1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
s = input()

len_s = len(s)
target_number = 2019
count = 0

for i in range(0, len_s - 3):
    for j in range(i + 4, len_s + 1):
        number = int(s[i:j])
#        print("number: {}".format(number))
        if number % target_number == 0:
            count += 1
#            print("can!")

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

dict = {}
for i in range(len(S)):
    for j in range(len(S), 0, -1):
        if j - i >= 4:
            if S[i:j] in dict:
                dict[S[i:j]] += 1
            else:
                dict[S[i:j]] = 1

cnt = 0
for key in dict:
    if int(key) % 2019 == 0:
        cnt += dict[key]
print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

from collections import deque

def main():
  d_origin = deque(input())

  ans = 0
  for i in range(len(d_origin)):
    d = d_origin.copy()
    for k in range(i):
      d.popleft()
    for j in range(len(d)):
      if int(''.join(d))%2019 == 0:
        ans += 1
      d.pop()
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

s = input()

c = 0

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

print(c)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
ans = 0
for i in range(len(S)):
    for j in range(i+1,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)
cnt = 0
for i in range(N-4):
    for j in range(i+3,N):
        if int(S[i:j+1]) % 2019 == 0:
            cnt += 1
        else:
            pass
print(cnt)