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:
def main():
    S = input()

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

    l = len(S)
    ans = 0
    for i in range(l-1,3,-1):
        tmp = ''.join([S[i-4],S[i-3],S[i-2],S[i-1],S[i]])
        if tmp not in simo5:
            continue
        else:
            if int(tmp)%2019 == 0:
                ans += 1
            cnt = 0
            for j in range(i-5,-1,-1):
                tmp = ''.join([S[j],tmp])
                if int(tmp)%2019 == 0:
                    ans += 1
                cnt += 1
                if cnt == 1000:
                    break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main(): 
  s_str = input()

  num = 0
  i=0
  for _ in tuple(range(0, len(s_str)-4)):
    j = i+3
    for _ in tuple(range(i+3, len(s_str))):
      tmp_str = s_str[i:j+1]
      if int(tmp_str)%2019==0:
        num+=1
      j+=1
    i+=1
  print(num)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())


s = list(map(int,list(input())[:-1]))
n=len(s)
right = [0] * (n + 1)
for i in range(n):
    right[-i - 2] = (right[-i - 1] + s[-i-1] * 10**i) % 2019

log = defaultdict(lambda: 0)

for i in range(n + 1):
    log[right[-i - 1]] += 1
ans=0
for key,value in log.items():
    if value > 1:
        ans += value * (value - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
S=input()

x=[i*2019 for i in range(1,5000)]


ans=0

for i in x:
    t=len(re.findall("(?={})".format(i),S))
    ans+=t

print(ans)

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):
            if S[i-1] == 0:
                continue
            if int(S[start:i]) % 2019 == 0:
                cnt += 1
                break
        start += 2
    print(cnt)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:

def solve(S):
    past_mods = {0: 1}
    M = 2019
    s = 0
    ans = 0
    for c in S:
        s = (s * 10 + int(c)) % M
        new_mods = {}
        for k, v in past_mods.items():
            mk = k*10 % M
            if (s - mk) % M == 0:
                ans += v
            new_mods[mk] = v
        new_mods.setdefault(s, 0)
        new_mods[s] += 1

        past_mods = new_mods
    return ans

if __name__ == "__main__":
    S = input()
    print(solve(S))

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0


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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = str(input())

    def is_3bai(n):
        if n % 3 == 0:
            return True
        else:
            return False

    def is_673bai(n):
        if n % 673 == 0:
            return True
        else:
            return False

    def ketawa(string):
        res = 0
        for s in string:
            res += int(s)
        return res

    sl = len(s)
    res = 0
    if sl >= 4:
        for i in range(sl - 4 + 1):
            sum_part = ketawa(s[i:i+3])
            for j in range(i + 3, sl):
                sum_part += int(s[j])
                if is_3bai(sum_part):
                    part = s[i:j+1]
                    if is_673bai(int(part)):
                        res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

x = 2019
S = input()
l = len(S)
S = int(S)

a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s = (S%10**(i+1))
#    b.append(s % x)
    xx[s%x] += 1

ans = 0
#for i in range(len(b)):
#    xx[b[i]] += 1
def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = str(input())

# check = []
count = 0
temp = ""

for j in range(len(N)):
    for i in range(0,len(N) - j):
        temp += N[i + j]
        if int(temp) % 2019 == 0:
            # check.append(temp)
            count += 1
            i -= 1
            temp = ""
    temp = ""
        
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

X = []
for i in range(0, len(S) - 4):
  for j in range(i + 4, len(S) + 1):
    X.append(int(S[i:j]))

Y = list(map(lambda x: x % 2019, X))
print(Y.count(0))

Submission status: Time Limit Exceeded

Solution code:
s=input()

k=0

for i in range(len(s)-3):

    for j in range(i+4,len(s)+1):

        if j<=i:

            pass

        else:

            if int(s[i:j])%2019 == 0:

                k+=1

            else:pass


print(k)

Submission status: Time Limit Exceeded

Solution code:
s=input()
k=2019
ans = 0
dp=[[0 for _ in range(k)] for _ in range(len(s))]
dp[0][int(s[0])] = 1
for i in range(1,len(s)):
    t = int(s[i])
    dp[i][t] += 1
    for j in range(k):
        dp[i][((10*j)+t)%k] += dp[i-1][j]
        #dp[i][j] += dp[i-1][j]
    ans += dp[i][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()

A = 0


while True:

    B = N[0:3]

    for C in range(len(N) - 3):

        D = C+3

        B += N[D]

        if int(int(B) % 2019) == 0:
            A += 1

    if len(N) < 5:
        break

    N = N[1:len(N)]

print(A)

Submission status: Time Limit Exceeded

Solution code:
S = input()

n = len(S)
memo = set()
ans = 0
for i in range(n):
    for j in range(i, n):
        v = int(S[i:j + 1])
        if v in memo or v  % 2019 == 0:
            ans += 1
            memo.add(v)
            
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
s = int(S)
n = len(S)
count = 0
for i in range(1,n+1):
    for j in range(i+4,n+1):
        si = s%10**(n-i+1)
        sij = si//10**(n-j)
        if sij % 2019 == 0:
            count+=1
            i+=3
            j+=3

print(count)

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque

S = list(input())
dp = [ [0]*2020 for _ in range(len(S)+1) ]
dp[0][0] = 1
A = [0]
for i in range(1,len(S)+1):
    q = deque(A)
    A = []
    while(len(q)>0):
        j = q.popleft()
        T = (j * 10 + int(S[i - 1])) % 2019
        dp[i][T] += dp[i-1][j]
        A.append(T)
    if i != 1:
        dp[i][int(S[i-1])] += 1
        A.append(int(S[i-1]))
    A = set(A)

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    s=input()
    cnt=0
    for i in range(len(s)):
        for j in range(i+4,len(s)+1):
            s1=int(s[i:j])
            if s1%3==0:
                if s1%673==0:
                    cnt+=1
    print(cnt)
resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
dp=[0 for i in range(N)]
check=[0 for i in range(N)]

List=[]
moji = ''
kireme=False
for i in range(N):
    moji+=S[i]
    dp[i]=dp[i-1]
    l=len(moji)
    for j in range(l):
        if int(moji[l-j-1:])%2019==0:
            List.append((i-j,i,int(moji[l-j-1:])))
            check[i]+=1+check[i-j-1]
            dp[i]+=1
            """
            if check[max(i-j-1,0)]:
                #check[i-j-1]+=1
                dp[i]+=check[i-j-1]
            """
            
#print(List)
#print(check)
#print(dp) 
print(dp[N-1])

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,len(S)+1):
		for j in range(len(S)):
			if i+j > len(S):
				break
			#tmpaaa = int(S[j:j+i])
			tmp = S_int // (10**(len(S)-(j+i)))
			tmp2 = str(tmp)
			tmp2 = tmp2[j:]
			tmp = int(tmp2)

			#print("{} {}".format(tmpaaa,tmp2))
			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()
l=len(S)
t=0
p=0
mm=[[0] * l for i in range(10)]

for i in range(10):
    for j in range(l):
        mm[i][j]=i*(10**j)%2019




for i in range(l-1,2,-1):

    p=0
    for j in range(i+1):


        p=(p+mm[int(S[i-j])][j])%2019

        if p==0:

            t+=1

print(t)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = list(str(n))

ans = 0

for i in range(len(a)-3):
    for j in range(len(a)-3-i):
        k = a[i:i+4+j]
        if len(k)==4 and int(k[0])%2 !=0:
            continue
        elif len(k)==4 and k[0]=="2" and k[1]!= "0":
            continue
        elif len(k)==5 and int(k[1])%2 != 0:
            continue
        elif len(k)==6 and int(k[2])%2 == 0:
            continue
        elif int("".join(map(str, k)))%2019 == 0:
            ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
cnt = 0

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=input()
ans = 0
for i in range(len(S)-4):
    K = str(int(S[i:])//2019)
    if '000' in K:
        ans +=1
    if int(S[i:])%2019==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys

#A, B, C, D = list(map(int, input().strip().split()))
S = input()
#maximum = sys.maxsize
maximum = 10**4
A = [str(i * 2019) for i in range(maximum) if '0' not in str(i * 2019)]
ans = 0

for a in A:  
  pattern_ex = '(?=(' + a + '))'
  tmp = len(re.findall(pattern_ex, S))
  #if tmp != 0:
  #  print(a, tmp)
  ans += tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)
ans = 0
if n <= 3:
    print(0)
    exit()
elif n == 4:
    if int(s[0]*1000+s[1]*100+s[2]*10+s[3]) % 2019 == 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
elif n > 4:
    for i in range(n-3):
        kar = int(s[i])*100 + int(s[i+1])*10 + int(s[i+2])
        for j in range(i+3,n):
            kar = (kar*10 + int(s[j])) %2019
            if kar == 0:
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
S_list = list(S)

# kは右から0, 1, ...。右側。
# lも同様、左側。(kより大きい)

result = 0

for k in range(len(S_list)):
  for l in range(len(S_list)):
    value = 0
    if k < l:
      for num in range(l - k + 1):
        newnum = len(S_list) - num - 1 - k
        # print (newnum)
        # print(num)
        if num >= 1:
          value += int(S_list[newnum]) * (10**num)
        else:
          value += int(S_list[newnum])
          
      
      if value % 2019 == 0:
        result += 1
        # print (value)

print (result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
n=int(input())
if n<10000:
  if n%2019 == 0:
    print(1)
  else:
    print(0)
else:
  x=deque(str(n))
  c=0
  used=[]
  for i in range(len(x)-4):
    if i not in used:
      for j in range(i+4, len(x)):
        if int(''.join(deque(itertools.islice(x, i, j+1)))) % 2019 == 0:
          c+=1
          used.append(i)
          i=j
          j+=4
  print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = str(input())
    S_len = len(S)
    count = 0
    if len(''.join(set(S))) == 1 :
        print ("0")
    else :
        for i in range(0,S_len-3) :
            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:
import re
S=input()

x=[i*2019 for i in range(1,10000)]


ans=0

for i in x:
    t=len(re.findall("(?={})".format(i),S))
    ans+=t

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S=input()
    N=len(S)
    A=[]
    cnt=0

    for n in range(1,100000):
        if '0' not in str(2019*n): 
            A.append(str(2019*n))

    for st in A:
        lenst=len(st)
        for i in range(N-lenst+1):
            if S[i:i+lenst]==st:
                cnt+=1
    print(cnt)

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:
  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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A=list(map(int,list(input())))
    N=len(A)
    d=[0]*2019
    for i in range(2019):
        d[i]=(i*10)%MOD
    dp=[[0]*2019 for _ in range(N+1)]
    ans=0
    for i,x in enumerate(A):
        for j in range(2019):
            dp[i+1][(d[j]+x)%MOD]+=dp[i][j]
        dp[i+1][x]+=1
        ans+=dp[i+1][0]
    print(ans)

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1

""" Input
N = int(input())
N, A, B = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

S = input().rstrip()

counter = 0
for l_index in range(len(S) - 4):
    atama = int(S[l_index:l_index+2])
    if atama % 2 != 0:
        continue
    else:
        r_index = 5
        top = l_index
        while True:
            saigo = l_index + r_index
            if saigo > len(S):
                break
            kouho = int(S[top:saigo])
            if kouho % 2019 == 0:
                counter += 1
                top = r_index
                r_index += 5
                continue
            r_index += 1


print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 0
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*(10**k)%2019
    n%=2019
    d[n] += 1
    k+=1

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
number = [ str(x*2019) for x in range(1000)]
count=0
v = []
for i in range(4, len(S)):
    for k in range(i):
        for l in range(0, len(S)//i):
            if len(S[l*i+k: l*i+k+i])==i:
                v.append(S[l*i+k: l*i+k+i])
for m in v:
    if m in number:
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

res = 0
dp_dict = {}

for i_upper in range(0, len(s)):
    temp_mod = 0
    temp_dp_dict = {}
    for i_lower in range(i_upper, len(s)):
        temp_mod = (temp_mod * 10 + int(s[i_lower])) % 2019

        if temp_mod == 0:
            if i_lower in dp_dict:
                res += dp_dict[i_lower]
                for key in temp_dp_dict:
                    temp_dp_dict[key] += dp_dict[i_lower]
                break
            res += 1
            temp_dp_dict[i_lower] = 0
            for key in temp_dp_dict:
                temp_dp_dict[key] += 1

    for key in temp_dp_dict:
        dp_dict[key] = temp_dp_dict[key]

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
num_list = []
list4 = []
for i in range(1,10001):
    num_list.append(i*2019)
    list4.append(int(str(i*2019)[-4::]))
for j in range(0,len(s)-4+1):
    if int(s[0+j:4+j]) in list4:
        
        if s[4+j-len(str(num_list[list4.index(int(s[0+j:4+j]))])):4+j] == str(num_list[list4.index(int(s[0+j:4+j]))]):
            cnt += 1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
s = input()
ans = 0
l = [0]*2019

for i in range(len(s)-1)[::-1]:
    num = int(s[i:])
    ans += l[num%2019]
    l[num%2019] += 1
#    print(l[0])
print(ans+l[0])

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:
N = input()
a = 0

for i in range(len(N)):
  if N[i] == 0:
    continue
  for j in range(len(N)):
    if i > j:
      continue
    if int(N[i:j + 1]) == 0:
      continue
    #print(N[i:j + 1])
    if int(N[i:j + 1]) % 2019 == 0:
      a += 1
      #print(N[i:j + 1])

print(a)

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

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
l=len(S)
t=0

for k in range(4,l+1):
   for i in range(l-k+1):

      if int(S[i:(i+k)])%2019==0:
         t+=1
print(t)

Submission status: Time Limit Exceeded

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


S = str(input())

#print(S[2:5])
len_s = len(S)
count = 0

for i in range(4,len_s+1):#文字数
    for j in range(0,len_s):#場所
#        print(j,j+i)
        if i-j < 4:
            break
        elif int(S[j:j+i])%2019 == 0:
            count += 1

            
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
S = input()
Smod = [0] * 2019
Smod[0] = 1
ans = 0
for i in range(len(S)-1, -1, -1):
  S_i = int(S[i:])
  ans += Smod[S_i%2019]
  Smod[S_i%2019] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
s_list = list(map(int,s))
s_list = s_list[::-1]

count = 0
for i in range(0,len(s_list)+1) :
  for j in range(i+4,len(s_list)+1) :
    x_list = s_list[i:j]
    x = 0
    for k in range(0,len(x_list)) :
      x += x_list[k]*(10**k)
    if x <= 2018 :
      break
    if x%2019 == 0 :
      count += 1
      
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len( S )
l = [ str( 2019 * i )  for i in range( 1, 200000 ) if i % 10 != 0 ]
cnt = 0
for i in l:
    if len( i ) > N:
        break
    Sd = S
    if i in S:
        add = Sd.find( i )
        while add != - 1:
            cnt += 1
            Sd = Sd[ add + 1: ]
            add = Sd.find( i )
print( cnt )

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = [0]*200000

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[r] += 1
            break;
        else:
            r += 1
ans[l] = ans[l]*ans[r]

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
S = input()
r, ans = 0, 0
for l in range(len(S)):
    while r < len(S):
        if int(S[l:r+1]) % 2019 == 0:
            ans += 1
            break
        r += 1
    r = l + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
x =input()
count = 0
while(True):
    for i in range(1,100):
        if 2019*i > int(x):
            break
        count += x.count(str(2019*i))
print(str(count))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())


s = list(map(int,list(input())[:-1]))
n=len(s)
left = [0]*(n+1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (left[i] * 10 + s[i]) % 2019
    right[-i - 2] = (right[-i - 1] + s[-i-1] * 10**i) % 2019

log = defaultdict(lambda: 0)

for i in range(n + 1):
    log[right[-i - 1]] += 1
ans=0
for key,value in log.items():
    if value > 1:
        ans += value * (value - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = list(input())
# Ns = ''.join(N)
M = list(map(str, list(range(len(N)))))
S = list(itertools.combinations(M,2))
count = 0
for _, combi in enumerate(S):
    X = int(combi[0])
    Y = int(combi[1])
    if Y - X > 2:
        A = N[X:Y+1]
        B = int(''.join(A))
        # print(A,B)
        if B%2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = input()
t = len(n)
total = 0
for i in range(t-4):
    for j in range(i+4,t):
        k = (n[i:j+1])
        l = int(k)
        if l%2019 == 0:
            total += 1
            break

print(total)

Submission status: Time Limit Exceeded

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

#jが来てあまりがiとなった時に元々のあまりはいくつか
dic = [[[] 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].append(i)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
N = len(S)
 
cnt = 0
alr = []
for i in range(N-3):
    if i in alr:
        continue
    else:
        cnt_i = 1
        for j in range(i+3,N):
            S_int = int(S[i:(j+1)])
            if S_int % 2019 == 0:
                cnt += cnt_i
                cnt_i += 1
                alr.append(j+1)
print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(N-4,-1,-1):
    for j in range(4,N+1):
        a = S%10**j
        if a%2019 == 0:
            ans+=1

    S //= 10
    N -= 1


print(ans)