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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S_int = int(S)

	target = 5
	ans = 0
	for i in range(target,100000):
		for j in range(len(S)):
			if i+j > len(S):
				break
			tmp = int(S[j:j+i])
			if tmp % 2019 == 0:
				ans += 1

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

def check_2019(txt):
  amari = int(txt) % 2019
  if amari == 0:
    return True
  else:
    return False

N = len(S)

ans = 0

i = 0
j = i + 3

while(i <= N):
  j = i+1
  while(j <= N):
    if check_2019(S[i:j]):
      ans += 1
      # i = j
      # break
    j += 1
  i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
for i in range(len(s)-3):
    while True:
        if s[i]  == '0':
            i += 1
        else:
            break
    tmp = s[i] + s[i+1] + s[i+2]
    for j in range(i+3, len(s)):
        tmp += s[j]
        if int(tmp)%2019 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import re
n = input()
n_num = int(n)
how = 2019
cnt=0

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

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-3): 
    for j in range(3,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:
from sys import stdin, stdout
s = stdin.readline().strip()
n = len(s)
k = 2019
cnt = 0
seenRem = []
for i in range(n):
    seenRem.append(set())
for i in range(n):
    rem = 0
    f = 0
    for j in range(i, n):
        rem = (10 * rem + int(s[j])) % k
        if rem in seenRem[j]:
            break
        seenRem[j].add(rem)
        if rem == 0:
            f += 1
    cnt += (f * ( f + 1) // 2)
stdout.write(str(cnt))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
S = input()
count = 0
imax = len(S)-3
jmax = len(S)
for i in range(0,imax):
  for j in range(i+3,jmax):
    if int(S[i:j+1])%2019 == 0:
      count += 1

print(count)

Submission status: Time Limit Exceeded

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

#jが来てあまりがiとなった時に元々のあまりはいくつか
dic = [[0 for j in range(10)] for i in range(2019)]

for i in range(2019):
    for j in range(1,9):
        tmp = (i*10+j)%mod
        dic[tmp][j] = i

# i桁までみたとき、あまりがjの物の個数
dp_sub = [[0 for j in range(2019)]for i in range(n+1)]
dp_sub[1][int(s[0])] = 1

# i桁までみたとき、あまりがjの物の個数
dp = [[0 for j in range(2019)]for i in range(n+1)]
dp[1][int(s[0])] = 1
for i in range(1,n):
    dp_sub[i+1][int(s[i])] = 1
    for j in range(2019):
        dp[i+1][j] = dp[i][j]
        dp_sub[i+1][j] += dp_sub[i][dic[j][int(s[i])]]
        dp[i+1][j] += dp_sub[i][dic[j][int(s[i])]]
print(dp[n][0])

Submission status: Time Limit Exceeded

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

ans=0
for m in range(4,n+1):
    for i in range(0,n-m+1):
        if int(s[i:i+m])%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mul2019(num):
    return 1 if num % 2019 == 0 else 0


S = str(input())
p = 0
num_list = []
for i in range(0, len(S)):
    for j in range(len(S), i, -1):
        if len(S[i:j]) >= 4 and int(S[i:j]) >= 2019:
            num_list.append(int(S[i:j]))

num_list = list(map(mul2019, num_list))
print(sum(num_list))

Submission status: Time Limit Exceeded

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

T = S()

def match(v):
    return int(v) % 2019 == 0

cnt = 0

M = {}

for i in range(0, len(T)):
    for j in range(i+1, len(T)+1):
        s = T[i:j]
        if s in M and M[s] == False:
            continue

        if match(s):
            M[s] = True
            cnt += 1
            continue

        M[s] = False

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
cnt = 0
S = S[::-1]
for i in range(0, len(S)-4):
    found_step = 0
    for j in range(i+5, len(S)+1):
        s = int(S[i+found_step:j][::-1])
        if s < 12114:
            continue
        elif s % 2019 == 0:
            found_step = j - i
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S = [str(s) for s in S]
if len(S) <=3:
    print("0")
    exit()
counter = 0
i = 0
for r in range(len(S)):
    for j in range(4, len(S)+1):
        # Jがリストの長さより大きくなったらBreak
        if i + j > len(S):
            break
        target = S[r:r+j]
        test= ''
        for t in target: 
            test += t
        if int(test) % 2019 == 0:
            counter+=1
            break
    i +=1
print(str(counter))

Submission status: Time Limit Exceeded

Solution code:
def check(s):
  count = 0
  for j in range(4, len(s)+1):
    for i in range(len(s) - j + 1):
      if int(''.join(s[i:i + j])) % 2019 == 0:
        count += 1
      if len(s) - j < 4:
        break
  print(count)

def main():
  s = tuple(input())
  check(s)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
S = input()
anskouho_set = set()
mod3 =[]
for x in S:
    mod3.append(int(x)%3)
mod3_accumulate = [x%3 for x in list(itertools.accumulate(mod3))]
ans = 0
for i in range(3):
    temp = []
    if i==0:
        temp.append(0)
    for j,x in enumerate(mod3_accumulate):
        if x==i:
            temp.append(j)
    for k in range(len(temp)):
        for l in range(k+1,len(temp)):
            if temp[l]-temp[k]>=4:
                anskouho_set.add((temp[k],temp[l]))
            if temp[l]+1-temp[k]>=4:
                anskouho_set.add((temp[k]+1,temp[l]))
for x in anskouho_set:
    if int(S[x[0]:x[1]+1])%2019==0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

if n<2019:
    print(0)
    exit()
dp=[]
for i in range(m+1):
    dp.append((n%(10**i))%2019)
def comb(n,m):
    import math
    if n-m<0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))
import collections
c=collections.Counter(dp)
ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=comb(j,2)
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(str(input()))
#    A = [k * 2019 for k in range(1,100)]
    cnt = 0
    if len(S) >= 4: # ToDo 4桁でカウント
        for keta in range(4,len(S)):
            for i in range(0,len(S)-keta+1):    # i ＝ idxの場所
#                NUM = ''.join(S[i:keta+i])
#                if int(NUM) in A: cnt+=1
#                if (int(NUM) % 2019 ) == 0: cnt += 1
                if (int(''.join(S[i:keta+i])) % 2019 ) == 0: cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

s = str(input())
tisa = []
for i in range(1,1000000):
  ww = str(2019*i)
  if '0' not in ww:
    tisa.append(ww)
#ok
#print(s)
#print(tisa)
#print(len(tisa))
#重複　count methodは無理
ans = 0
for c in tisa:
  if c in s:
    i = 0
    while i <len(s)-len(c)+1:
      if s[i:i+len(c)]==c:
        ans += 1
        i += 3
      else :
        i += 1
    

      
  

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

ori_size = len(S)
count = 0
for i in range(ori_size-2):
    for j in range(i+4, ori_size+1):
        num = int(S[i:j])
        if num % 3 == 0 and num % 673 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

# """nを素因数分解"""
# """2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
# print(factorization(m))
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

S = input()

count = 0
for i in range(4,2*(10**5)):
    for j in range(len(S)-i):
        l = j
        r = j + i
        if int(S[l:r+1])%2019==0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = list(map(int, input()))
n = len(S)
 
fl = [False]*(n+1)
res = 0
 
for i in range(n-3):
    if fl[i]:
        continue
    
    x = 0
    cnt = 0
    for j in range(i, n):
        x *= 10
        x += S[j]
        x %= 2019
        if x == 0:
            cnt += 1
            fl[j+1] = True
            
    
    res += (cnt+1)*cnt//2
 
print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = []
count = 0

for s in S:
  mod.append(int(s)%3)
  
for i in range(len(S)-3):
  m = (mod[i]+mod[i+1]+mod[i+2])%3
  j = i+3
  while j<len(S):
    m += mod[j]
    if m%3 == 0:
      if int(S[i:j+1])%2019 == 0:
        count += 1
        if len(S)-j<3:
          break
        else:
          m += mod[j+1]+mod[j+2]+mod[j+3]
          j += 3
    j += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
long = len(S)
ans = 0
modlist = [0]
mod = 0
for i in reversed(range(long)):
    mod = (mod + 10 ** (long - i - 1) * int(S[i])) % 2019
    modlist.append(mod)
c = Counter(modlist)
for i in c.values(): ans += i * (i - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
d_n=0
i=5
for e in range(len(s)):
  for e2 in range(len(s[e:])):
    if len(s)<i+e+e2:
      break
    if int(s[e:e+i+e2])%2019==0:
      d_n+=1
print(d_n)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

d = len(S)
ans = 0
for i in range(4,d+1):
    t = int(S[0:i])
    for j in range(d-i+1):
        if t % 2019 == 0:
            ans += 1
        else:
            pass

        if j == d-i:
            pass
        else:
            t =  - int(S[j])*(10**i) + t*10 + int(S[i+j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()
length = len(S)
arr = np.array([int(S[i:j]) for i in range(0,length-3) for j in range(i+4, length+1)])
arr2 = arr % 2019
print(len(arr2)- np.count_nonzero(arr2))

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math


#計算量を無視して愚直に実装してみる
S = input() #文字列型で受け取る
N = len(S)
#print(len(S))

a = []
tmp = 0
for i in range(N):
    tmp = (tmp + int(S[i])) % 3
    a.append(tmp)
#print(a)




b = [(n+1)%3 for n in a]
c = [(n+2)%3 for n in a]
#print(b)
#print(c)

a_0 = []
b_0 = []
c_0 = []

for i in range(N):
    if(a[i] == 0):
        a_0.append(i)
    elif(b[i] == 0):
        b_0.append(i)
    else:
        c_0.append(i)
#print(a_0)
#print(b_0)
#print(c_0)

status = 'a'
counter = 0
#start = 0 #スタート地点最初は0
for start in range(N):
    #print('start:{}'.format(start))
    if(status == 'a'):
        for goal in a_0:
            if(start < goal):
                s = S[start:goal+1]
                #print(s)
                if(int(s) % 2019 == 0):
                    counter += 1
        if(int(S[start]) % 3 == 1):
            status = 'c'
        elif(int(S[start]) % 3 == 2):
            status = 'b'
    elif(status == 'b'):
        for goal in b_0:
            if(start < goal):
                s = S[start:goal+1]
                #print(s)
                if(int(s) % 2019 == 0):
                    counter += 1
        if(int(S[start]) % 3 == 1):
            status = 'a'
        elif(int(S[start]) % 3 == 2):
            status = 'c'
    elif(status == 'c'):
        for goal in c_0:
            if(start < goal):
                s = S[start:goal+1]
                #print(s)
                if(int(s) % 2019 == 0):
                    counter += 1
        if(int(S[start]) % 3 == 1):
            status = 'b'
        elif(int(S[start]) % 3 == 2):
            status = 'a'
print(counter)





'''
#5桁以上しか探索しないコード
sg = []
for i in range(N):
    j = 5
    while i+j <= N:
        sg.append([i, i+j])
        j += 1
#print(sg)
counter = 0
for i in range(len(sg)):
    s = S[sg[i][0]:sg[i][1]]
    if(int(s)%2019==0):
        counter += 1
        print('hit at s:{}, len(s):{}'.format(s, len(s)))
print(counter)
'''


'''
index = [i for i in range(len(S))]
combi = list(combinations(index, 2))
#print(combi)

counter = 0
for i in range(len(combi)):
    #print()
    #print('start:{},goal:{}'.format(combi[i][0], combi[i][1]+1))
    s = S[combi[i][0]:combi[i][1]+1]
    #print('s:{},s%2019:{}'.format(s, int(s)%2019))
    #print()
    if(int(s) % 2019 == 0):
        #print('hit')
        counter += 1
print(counter)
'''


'''
#実験1
def is_there_0(K):
    #文字列入力
    ret = 'No'
    for i in range(len(K)):
        if(K[i] == '0'):
            ret = 'Yes'
    return ret

for i in range(1000000000000000):
    if(is_there_0(str(2019*i)) == 'No'):
        print('i:{}, 2019*i:{},len(s):{}'.format(i, 2019*i, len(str(2019*i))))
'''
'''
for i in range(10):
    print((i*100000)%2019)
'''




















'''
#実験2
l = []
for i in range(10000):
    l.append( (2019*i)%10000 )

l = sorted(l)
#print(l)
print(len(l))
'''

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = list()
for i in range((len(s)-3)):
  for j in range(3,(len(s)+1)):
    if not s[i:j]:
      continue
    else:
      l.append(int(s[i:j]))  
ll = list()
for c in range(len(l)):
  if l[c]%2019 == 0:
    ll.append(1)
  else:
    ll.append(0)
print(ll.count(1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def solver(n,i,before,keta):
    if len(n)>=i+keta-1:
        A5 = int("".join(n[i:i+keta]))
        if A5 in L:
            return solver2(n,i+keta,before+1)
        else:
            return before
    else:
        return before
def solver2(n,i,before):
    z = 0
    if len(n) < i:
        return 0
    if len(n) < i+3:
        return before
    for x in range(0,4):
        z += solver(n,i,before,x+5)
    if before ==0:
        return solver2(n,i+1,0)+z
    else:
        return before
    
    
N = input()
M = [0]*len(N)
L =[]
r =2019
for x in range (10001):
    a=r*x
    A =list(str(a))
    if "0" in A:
        pass
    else:    
        L.append(a)

ans = solver2(str(N),0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
l=len(S)
z=0
K=[]
for x in range(l):
    for y in range(l-x-3):
        T=S[x:x+y+4]
        t=int(T)
        if t==2019 or t==4038 or t==6057 or t==8076 or t==10095 or t>10095:
            K.append(t)

K=[x%2019 for x in K]
print(K.count(0))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
c = 0
memo = []

for x in range(len(S)):
  for y in range(len(S)):
    if (len(S[x:y+1]) == 0):
      continue
    solve = int(''.join(S[x:y+1]))
    if 2 <= memo.count(solve):
      continue
    if solve % 2019 == 0:
      c += 1
      memo.append(solve)
    else:
      memo.append(solve)
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

cnt = 0

for i in range(nn-3):
  a = el[i]+el[i+1]+el[i+2]
  #print('i:',el[i],el[i+1],el[i+2],'a:',a)
  for j in range(i+3,nn):
    a += el[j]
    if a % 3 == 0:
      #print(i+1,j+1,s[i:j+1])
      ns= int(s[i:j+1])
      if ns % 2019 == 0 :
        cnt += 1

print(cnt)

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
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = len(S)
ans = 0
c = 0

# while N-c+1 >= 4:
#     for i in range(c+3,N):
#         n = int(S[c:i+1])
#         if n > 0 and n % 2019 == 0:
#             print(n)
#             ans += 1
#         else:
#             continue

#     c += 1


for i in range(N-3):
    left = i
    right = left+3
    while right <= N:
        n = int(S[left :right])

        if n > 0 and n % 2019 == 0:
            # print(n)
            ans += 1
        right += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [0]*2020
if len(S) < 4:
    print(0)
    exit(0)

T = []
t = int(S[0])
T.append(t)
for k in range(1,len(S)):
    t = t*10 + int(S[k])
    t %= 2019
    T.append(t)

U = [0]
s = int(S[-1])
U.append(s)
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(10**(len(S)-k-1)) + s
    s %= 2019
    U.append(s)
ans = 0
U = sorted(U)
for k in range(1,len(U)):
    if U[k-1] == U[k]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
res = 0
cur = 0
count = [0] * 2020
for i, c in enumerate(map(int, S)):
    cur = cur * 10 + c
    if cur % 2019 == 0:
        res += 1
    temp = (cur * 10 ** (n - i)) % 2019
    res += count[temp]
    count[temp] += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
from itertools import product, permutations,combinations


l = len(s) +1
A = [i for i in range(l)]

cnt = 0
ans = []

for i in combinations(A,2):
    
    ans = s[i[0]:i[1]]
    if int("".join(map(str, ans)))%2019==0:
            cnt +=1
    
        
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
Ss=input()
order=len(Ss);
S=int(Ss)
N=0
if(S<2019):
    print(N)
else:
    for j in range(order-1,2,-1):
        for i in range(j-3,-1,-1):
            ij=int(Ss[i:j+1])
            if(ij%2019==0):
                N+=1
                i-=4
            
    print(N)

Submission status: Time Limit Exceeded

Solution code:
S= str(input())
A= list(map(int,S))
l = len(A)
cnt=0

for i in range(l-1):
    for j in range(i+1,l):
        T= S[i:j+1]
        t= int(T)
        if t%2019==0:
            cnt+=1
        else:
            cnt+=0
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    multipuls = []
    answers = []

    # 事前に2019の倍数を作っておいた方がコスト削減になるかと思ったが、
    # あまり意味がない気がしてきたのでやめる
    # i = 1
    # while True:
    #     if 2019 * i > 200000:
    #         break
    #     multipuls.append(2019 * i)
    #     i += 1

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

    print(len(answers))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
 
m_len=len(s)+1
count = 0
for i in range(5,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:
s=input()
i=1
j=2
count=0
while i<len(s):
    a=int(s[i-1:j])
    if a%2019 == 0:
        count+=1
    if j>=len(s):
        i+=1
        j=i+1
    else:
        j+=1      
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
string=input()
count=0
times=1
length=4
while len(string) > 3:
  target=int(string[:length])
  if target % 2019 == 0:
    count+=1
  length+=1
  if length == 2000000 or len(string) < length:
    length=4
    string=string[1:]
  times+=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, len(S)):
		if int(S[i:j+1]) % 2019 == 0:
			count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = list(input(''))

count = 0
sta = 0
tp = 0
#kaisuu = 0

for i in range(sta,len(s)+1):
    tp = 0
    for j in range(i+1,len(s)+1):
        # kaisuu += 1
        # print('回数：',kaisuu)
        slice_s = s[i:j]
        num = int(''.join(slice_s))
        if num % 2019 == 0:
            #print('i=',i)
            count += 1
            tp = 1
        if tp == 1:
            continue
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
P = "2019"
cnt = 0
while(len(S) > len(P)):
    if(P.count("0") == 0):
        cnt += S.count(P)
    while(P.count("0") != 0):
        P = str(int(P) + 2019)
print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
# flag = False
# tmp_j = 0
# for i in range(len_S-4):
#     if flag:
#         flag = False
#         i = tmp_j
#     for j in range(i+3, len_S):
#         tmp = int(S[i:j+1])
#         if tmp % 2019 == 0:
#             cnt += 1
#             tmp_j = j
#             flag = True
#             break

import itertools
lst = (list(itertools.combinations(range(len_S), 2)))
for l in lst:
    i = l[0]
    j = l[1]
    if int(S[i:j+1]) % 2019 == 0:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = list(s)
dp = [[0 for i in range(2019)] for i in range(len(l)+1)]
mod = 2019
ans = 0
for i in range(len(s)):
    dp[i+1][int(l[i])] += 1
    for j in range(2019):
        dp[i+1][(10 * j + int(l[i])) % 2019] += dp[i][j]
for i in range(1, len(l)+1):
    ans += dp[i][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
ans = 0
for i in range(2018):
  m = lst.count(i)
  ans += m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
n=len(str(s))
t=0
for j in range(n):
    j+=1
    for i in range(j-3):
        i+=1
        k=s
        k//=10**(n-j)
        k%=10**(j-i+1)
        if k==0:
            k=1
        if k%2019==0:
            t+=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
strS = input()
maxlength = len(strS)
count = 0
 
for i in range(maxlength -3):
  #print("i:{}".format(i))
  for j in range(maxlength - (i+4)):
    #print("j:{}".format(j))
    #print(strS[i:i+5+j])
    trynum = int(strS[i:i+5+j])
    if ( trynum % 2019 == 0 ):
      count += 1
 
print(count)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    #cnt=0
    k=list(s)
    d=[0]*2019
    for i in range(len(k)):
        d[int(s[i:])%2019]+=1
    
    cnt=d[0]
    for i in range(2019):
        cnt+=d[i]*(d[i]-1)//2
            #print(s[i:j+1])
    print(cnt)
    #print(d)
main()

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]
        n = 0
        for k in range(len(L)):
            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:
s=input()
n=len(s)
count=0
for i in range(n-3):
  for j in range(i,n+1):
    for k in range(100):
      sa=str(2019*k)
      if s[i:j]==sa:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S=input()
U=int(S)
T=len(S)

list=[]
count=0
for i in range(0,T-3):
  for j in range(i+4,T+1):
    list.append(S[i:j])
list_2 = [int(n) for n in list if int(n)%2019==0]
print(len(list_2))