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,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:

    def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        #set_val
        if init_ls==None:
            for i in range(n):
                self.seg[i+self.num-1]=init_val
        else:
            for i in range(n):
                self.seg[i+self.num-1]=init_ls[i]
        #build
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p >>= 1
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        # 生配列を表示
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


ans=0

s=input()
n=len(s)
a=[0]
t=0
m=2019
d=0
for i in s[::-1]:
    t=t+int(i)*10**d
    d+=1
    a.append(t%m)
#    show(t)



c=Counter(a)

#for i in range(n):
for i,j in c.items():
    ans+=j*(j-1)//2
#    show(i,j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
count = 0
for i in range(N):
    for j in range(i + 3, N):
        if int("".join(S[i : j+1])) % 2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
cnt=0
for i in range(len(S)):
    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=str(input())
m=0
A=[i*2019 for i in range(1,200000)]
for j in range(len(S)-3):
  i=j+3
  while True:
    if int(S[j:i]) in A:
      m+=1
print(m)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
cnt = 0
for i in range(len(S)-3):
	for j in range(i+3, 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)

ans = 0
for i in range(0,n+1):
    for j in range(i+4,n+1):
        if int(S[i:j])%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):
        tp = s[i:j]
        #print(tp)
        tx = sum([int(i) for i in tp])
        if (tx % 3 == 0 and int(tp) % 673 == 0):
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
S=S+'0'
length=len(S)

count={}

for i in range(length):
    count[int(S[i:])%2019]=count.get(int(S[i:])%2019,0)+1

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

print(retval)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0
for l in range(0, len_s-3):
    for r in range(l+4, len_s+1):
        if int(s[l:r]) % 2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0
r = 0
tmp = 0
for l in range(len(S)):
    r = l + 4
    while r <= len(S):
        s = S[l:r]
        tmp = int(s)
        if tmp % 2019 == 0:
            ans += 1

        r += 1


print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

# do shakutori


Q = [0]
for i in range(len(S)-1, -1, -1):
    Q.append(int(S[i:]) % 2019)
# print(Q)

import collections
dct = dict(collections.Counter(Q))
# print(dct)
ans = 0
for val in dct.values():
    ans += val * (val - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    p = 2019
    d = {i:0 for i in range(p)}
    d[0] = 1
    r = 0
    x = 0
    for i in range(len(S)):
        x += int(S[len(S)-1-i]) * pow(10, i)
        x %= p
        r += d[x]
        d[x] += 1
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    # S = '1817181712114'
    S = input()

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# N = int(input())
# K = list(map(int, input().split()))
# N, M = map(int, input().split())

S = list(input())

cnt = 0

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

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s = input()
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
for i in range(l):
    k = int(s[i:]) % 2019
    x[k] += 1

ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

S = list(input())
L = len(S)

c = 0
t = 0
md = [0] * 2019
md[0] += 1
for i in range(L - 1, -1, -1):
    t += int(S[i]) * pow(10, c)
    c += 1
    md[t % 2019] += 1

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#d

x = input()
s = len(x)

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=str(input())

n=len(s)

cnt=0

for i in range(n):
  for j in range(i+1,n+1):
    a=int(s[i:j])

    if a%2019==0:
      cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

A = []

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

print(len(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
p=0
cnt=0
while(p!=len(S)):
    for i in range(p+3,len(S)+1):
        if int(S[p:i])%2019==0:
            cnt+=1
    p+=1
print(cnt)

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    S = input()
    
    l = []
    base = 1
    for st in S[::-1]:
        l.append((int(st)*base)%2019)
        base *= 10
        
    cum = 0
    d = defaultdict(int)
    d[0] = 1
    
    for num in l:
        cum += num
        d[cum%2019] += 1

    ans = 0
    for num in d.values():
        ans += (num*(num-1))//2
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def part(i, j, list):
    return int("".join(list[i:j]))


N = list(input())
N_len = len(N)
cnt = 0

for i in range(N_len+1):
    for j in range(i+1, N_len+1):
        if part(i, j, N) % 2019 == 0:
            #print(i, j)
            cnt += 1


print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
MOD = 2019

dp = [[0] * (MOD) for i in range(len(s) + 1)]

dp[0][0] = 0
for i in range(len(s)):
    tmp = int(s[i])
    for val in range(MOD):
        dp[i + 1][((val * 10) + tmp) % MOD] += dp[i][val]
    dp[i + 1][tmp] += 1

ans = 0
for i in range(len(s) + 1):
    ans += dp[i][0]
    
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = '0' + input()
n = len(s)
cnt = 0

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

print(cnt)

Submission status: Time Limit Exceeded

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


S = list(input())
N = len(S)
MOD = 2019
#%%
A = [0]*(N+1)
R = [0]*(2030)

R[0] += 1
base = 1
for i in range(N):
    A[i+1] = A[i] + base*int(S[N-1-i])
    base *= 10
    A[i+1] %= MOD
    R[A[i+1]] += 1

ans = 0
for r in R:
    ans += r*(r-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = len(S)

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

Submission status: Time Limit Exceeded

Solution code:

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
n = len(S)
mod = 2019
s = [0]*(n+1)
for i in range(n):
    s[i+1] = (s[i]+int(S[n-i-1])*10**i)%mod
c = Counter(s)
ans = 0
for x in c.values():
    ans += x-1
print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
s=input()
n=len(s)
a=[]
x=0
for i in range(n):
	j = n-1-i
	c = int(s[j])
	x += (10**i)*c
	x %= 2019
	a.append(x)
c=collections.Counter(a)
ans = 0
for k,v in c.items():
	if k==0:
		ans += v
	else:
		ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
cnt = 0
for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        if not "0" in S[i:j] and int(S[i:j])%2019 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s_l = list(input())

ans = 0
for i in range(len(s_l)-1):
    for j in range(i,len(s_l)):
        val = int(''.join(s_l[i:j+1]))
        if val%2019 == 0 and val != 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

match = 0
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        val = int(s[i:j])
        if val >= 2019 and val % 2019 == 0:
            match += 1

print(match)

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

M = 2019
s = input()
n = len(s)
s = list(s)

out = 0
for i in range(n): 
    cur = 0
    for j in range(i, n):
        cur = cur * 10 + int(s[j])
        cur = cur % M
        if cur % M == 0:
            out += 1

print(out)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
s += '0'
s = s[::-1]

res = [-1]*(len(s)+1)
mod = 2019
cnt = {}
ans = 0
for i in range(len(s)):
    x = int(s[:i+1][::-1])%mod
    if x not in cnt:cnt[x] = 0
    ans += cnt[x]
    cnt[x] +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
#何桁とるかで考える
count = 0
for i in range(len(s)):
    if i <= 3:
        continue
    else:
        for j in range(len(s)):
            if i+j <= len(s):
                if int(s[j:j+i])%2019 == 0:
                    count += 1
                
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    S = input()
    cnt = 0
    start = 0
    while start+4 < len(S):
        for i in range(start+4,len(S)+1):
            #print(S[start:i])
            if int(S[start:i]) % 2019 == 0:
                cnt += 1
        start += 1
    print(cnt)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

count=0
l = len(s)
for i in range(l):
    for j in range(i):
        if int(''.join(s[j:i+1]))%2019 ==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

S=input()
N=len(S)
mod=2019
data=[(int(S[-i-1])*pow(10,i)) for i in range(0,N)]

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

answers = []
for start in range(len(s)-3):
    for end in range(start+4, len(s)+1):
        if int(s[start:end]) % 2019 == 0:
            answers.append((start, end))
print(len(answers))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    m = 2019
    dp = [0]*m
    ans = 0
    for i in s:
        i = int(i)
        dp[0] += 1
        dp2 = [0]*m
        for j in range(m):
            dp2[(j*10+i) % m] += dp[j]
        dp = dp2
        ans += dp[0]
    print(ans)


main()

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
p=0
cnt=0
while(p!=len(S)):
    for i in range(p+1,len(S)+1):
        if int(S[p:i])%2019==0:
            cnt+=1
    p+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from collections import deque

# sys.setrecursionlimit(100001)
INF = sys.maxsize


# ===CODE===
def main():
    n = input()

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

Submission status: Time Limit Exceeded

Solution code:
n = input()
l = len(n)
a = [0 for _ in range(2019)]
a[0] = 1
now = 0
for i in range(l)[::-1]:
  now += (10**(l-1-i))*int(n[i])
  now %= 2019
  a[now] += 1
  #print(now)
ans = 0
for d in range(2019):
  ans += a[d] * (a[d]-1) // 2
print(ans)

Submission status: Time Limit Exceeded

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

print(count)