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:
s = input()

res = 0
for i in range(len(s)):
    for k in range(i+4, len(s)+1):
        if int(s[i:k]) % 2019 == 0:
            res += 1

print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# python3
# -*- coding: utf-8 -*-
import sys
import math
import bisect
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
lmtx = lambda h: [list(map(int, lmis())) for _ in range(h)]
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


# main
s = input()

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

print(c)

Submission status: Time Limit Exceeded

Solution code:
# 文字列を一つ入力
S = input()

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s)
mod=2019
x=[(int(s[i])*(pow(10,l-i-1)))%2019 for i in range(l)]
y=[0]*l
y[0]=x[0]%mod
for i in range(1,l):
  y[i]=(y[i-1]+x[i])%mod
cnt=y.count(0)
print(l-len(set(y))+cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

cnt = 0

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

Submission status: Time Limit Exceeded

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

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:
s = input()
l = len(s)

ans = 0
for i in range(5,l):
    for k in range(0,l-i+1):
        ss = int(s[k:k+i])
        if ss% 2019 == 0:
            ans += 1
print(ans)

# for i in range(20):
#     print(2019*i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#D - Multiple of 2019
S = input()
cnt =0

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

Submission status: Time Limit Exceeded

Solution code:

s = input()
number = 0
for i in range(0,len(s)- 3):
    for j in range(i+3,len(s)):
        sum = 0
        for k in range(j-i+1):
            sum = sum + int(s[j- k]) * (10 ** (k))
            #print(sum)
        if sum % 2019 == 0:
            number = number + 1
print(number)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
#print(S)
D={}
ans=0
for i in range(len(S)):
    d={}
    d[int(S[i])]=1
    for k,v in D.items():
        if (k*10+int(S[i]))%2019 not in d:
            d[(k*10+int(S[i]))%2019]=v
        else:
            d[(k*10+int(S[i]))%2019]+=v
    if 0 in d:
        ans+=d[0]
    D=d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
def run():

    S = input()
    mods = [[] for _ in range(2019)]
    mods[0].append(0)
    for i in range(1, len(S)+1):
        tmp = int(S[-i:]) % 2019
        mods[tmp].append(i)

    count = 0
    for ns in mods:
        l = len(ns)
        count += l * (l-1) // 2
    print(count)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len_S-4):
    for j in range(i+3, len_S):
        tmp = int(S[i:j+1])

        if tmp % 2019 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
x=input()
list = list(map(int, x))

tmp=0
ans=0
for i in range(len(list)-3):
	tmp=list[i]*1000+list[i+1]*100+list[i+2]*10+list[i+3]
	if tmp%2019==0:
		ans=ans+1
	if i+4<=len(list):
		for j in range(i+4,len(list)):
			tmp=tmp*10+list[j]
			if tmp%2019==0:
				ans=ans+1
				
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    s = list(input())
    n = len(s)
    dp = [[[0 for _ in range(2019)] for _ in range(2)] for _ in range(n+1)]
    for i in range(n):
        for j in range(2019):
            dp[i+1][1][j] += dp[i][0][j]
            dp[i+1][1][j] += dp[i][1][j]
            dp[i+1][0][((j*10)+int(s[i]))%2019] += dp[i][0][j]
        dp[i+1][0][int(s[i])] += 1
    print(dp[n][0][0]+dp[n][1][0])
    
if __name__ == "__main__":
    main()

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
ls = len(S)
res = 0

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
def subString(s, n): 
	cnt = 0
	for i in range(n): 
	    for len in range(i+4,n+1): 
	        Str = s[i: len];
	        if(int(Str)%2019 == 0):
	        	cnt += 1; 
	print(cnt)

s = str(input())
subString(s, len(s))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def main():
# 整数の入力
    
    s = input()
    length = len(s)
    l = []
    for i in range(length):
        if length - i >= 4:

            for j in range(length - i):
                if j + 1 >= 4:
                    slice = s[i:i+j+1]
                    n = int(slice)
                    if n % 2019 == 0:
                        l.append(n)

    # 出力
    print(len(l))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input('')

n=0
for a in s:
    n=n+1

p=0
for i in range(n-1):
    t=''
    for j in range(n-i):
        t=t+s[i+j]
        if int(t)%2019==0:
            p=p+1

print(p)

Submission status: Time Limit Exceeded

Solution code:

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

     
q4()

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

Submission status: Time Limit Exceeded

Solution code:
def countSubStr(str, l, k): 
    count = 0
  
    for i in range(l): 
        n = 0
  
        # Take all sub-strings starting from i 
        for j in range(i, l, 1): 
            n = n * 10 + (ord(str[j]) - ord('0')) 
  
            # If current sub-string is divisible by k 
            if (n % k == 0): 
                count += 1
    return count 
  
# Driver code 
if __name__ == '__main__': 
    str = input()
    l = len(str) 
    k = 2019
    print(countSubStr(str, l, k))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

s = input()
num = len(s)
# print(int(s[1:5]))
ans = 0

for i in range(0, num + 1):
    for j in range(1, num + 1):
        test = s[i:j]
        # print(test)
        if len(test) <= 3:
            continue
        elif len(test) == 4 and int(test[0]) <= 1:
            continue
        if int(test) % 2019 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
# print(s)
l = []
for i in range(len(s)-3):
    for j in range(i+4, len(s)+1):
        # print(s[i:j])
        judge = int(''.join(s[i:j]))
        # print(i,j,judge)
        if judge>=2019 and judge%2019==0:
            l.append(judge)
print(len(l))

Submission status: Time Limit Exceeded

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
l = len(S)
ans = 0
for i in range(l-4):
    j = 4
    while 1:
        x = S[i:i+j]
        #print(x, (int(x) % 2019 == 0), i, j)
        if j == 4 and x[0] == '1':
            j += 1
        elif int(x) % 2019 == 0:
            ans += 1
            j += 4
        else:
            j += 1
        if i + j > l:
            break 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import fractions

s = stdin.readline().rstrip()

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7


def main():
    S = input()
    answer = 0
    for i in range(len(S)):
        func = lambda x, y: (int(x) * 10 + int(y)) % 2019
        A = list(accumulate(S[i:], func, initial=0))
        answer += A.count(0) - 1
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(count)

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

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
N = len(S)
l = 0
r = 0


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

from collections import Counter
c = Counter(amari).most_common()

ans = 0
for i in c:
  if i[1] != 0:
    ans += i[1] * (i[1]-1) // 2
  if i[0] == 0:
    ans += i[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = input()
ans =0
nums =""
for i in range(len(s)):
    for j in range(i+1,len(s)):
        for k in range(i,j+1):
            nums += s[k]
        num =int(nums)
        nums=""
        if num%2019==0:
            ans+=1
            #print(i,j,num)



print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = input() #1行目のNを取得する
l = len(n)

count = 0

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
#S = input()
S = "1" * 200000

# 求解処理
size = len(S)
result = 0
for i in range(size-3):
    for j in range(i, size):
        number = int(S[i:j+1])
        if number % 2019 == 0:
            result += 1

# 結果出力
print(result)

Submission status: Time Limit Exceeded

Solution code:


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

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

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

Submission status: Time Limit Exceeded

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

    roop_num = len(inputs)

    cnt = 0
    for start in range(roop_num):
        roop_num_end = roop_num - start
        for end in range(roop_num_end):
            end += start
            num = int(inputs[start:end+1])

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

    print(cnt)

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

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
if N<4:
  print(0)
  exit(0)
M=2019
X=[0]+[int(S[i])*pow(10,N-1-i)%M for i in range(N)]
import itertools
X = list(itertools.accumulate(X))
ans=0
for l in range(N-2):
  for r in range(l+4,N+1):
    if (X[l]-X[r])%M==0:
      ans+=1
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
ans = 0
for i in range(4, len(s) + 1):
    l = 0
    r = l + i
    while r <= len(s):
        if int(''.join(s[l:r])) % 2019 == 0:
            ans += 1
            l = r - 1
            r = l + i
        else:
            l += 1
            r += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()

res = 0

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

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len_S-2):
    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 = list(input())

ans = 0
tmp = 10**9
for i in range(len(s)-3):
    if i == tmp:
        pass
    for y in range(i+3, len(s)):
        if int("".join(s[i:y+1])) % 2019 == 0:
            ans += 1
            tmp = y+1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    S=sys.stdin.readline().strip()
    L=[0]*len(S)

    now=0
    for i in range(len(S)):
        now+=int(S[-i-1])*10**i
        L[-i-1]=now%2019

    dic=defaultdict(int)
    for a in L:
        dic[a]+=1

    
    output=0
    for _,val in dic.items():
        output+=val*(val-1)//2
    
    output+=dic[0]
    print(output)

main()

Submission status: Time Limit Exceeded

Solution code:
n = input()

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

print(count)

Submission status: Time Limit Exceeded

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

ans = 0

i = 0
while i < l - 3:
  j = i + 3
  while j < l:
    if int(s[i:j + 1]) % 2019 == 0:
      ans += 1
    j += 1
  i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    # 2019 = 3 * 673
    S = input()
    length = len(S)
    count = 0
    for start in range(0, length-3):
        now = length
        while now - start >= 4:
            s = S[start:now]
            if int(s) % 2019 == 0:
                count += 1
            now -= 1
    
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
ans = 0
i = 0
while i < N-4:
    j = 0
    while N-i-j-4 >= 0:
        if int(S[N-i-j-4:N-i]) % 2019 == 0:
            ans += 1
            i += 3
        j += 1
    i += 1
print(ans)

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



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

    if len(S) < 4:
        print(0)
        exit()
    if len(S) == 4:
        if int(S) % 2019 == 0:
            print(1)
            exit()
        else:
            print(0)
            exit()

    length = len(S)
    l, r = 0, 4
    while l < length-4:
        test = S[l:r]
        if int(test) % 2019 == 0:
            cnt += 1
        if r < length:
            r += 1
        else:
            l += 1
            r = l + 4
    # 出力
    print(cnt)

Submission status: Time Limit Exceeded

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

res = 0

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

print(count)

Submission status: Time Limit Exceeded

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

    return len(s_set)

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

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:
            ans += 1
        else:
            continue

    c += 1

print(ans)

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]

	target = 5
	ans = 0
	for i in range(target,len(S)):
		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()