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

Submission status: Time Limit Exceeded

Solution code:
s = input()
ls = len(s)
l_2019_set = set(list(range(2019, 20190000, 2019)))
ans = 0
for i in range(ls-3):
    for j in range(i+3, ls+1):
        if int(s[i:j]) in l_2019_set:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations

s = input()

a = np.append(0, np.cumsum(np.array(list(s), dtype=np.int64))%3)
x = np.where(a==0)[0].tolist()
y = np.where(a==1)[0].tolist()
z = np.where(a==2)[0].tolist()

ans = 0
for i,j in combinations(x,2):
    if eval(s[i:j] + " % 2019") == 0:
            ans += 1
for i,j in combinations(y,2):
    if eval(s[i:j] + " % 2019") == 0:
            ans += 1
for i,j in combinations(z,2):
    if eval(s[i:j] + " % 2019") == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
l = [0]* len(S)
for i in range(len(S)):
    T = S[:(i + 1)]
    t = int(T)
    l[i] = t * 10 ** (len(S) - i - 1)%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
print(sum(m) + l.count(0))

Submission status: Time Limit Exceeded

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

for begindigit in range(0, digitnum - 4):
    for enddigit in range(begindigit + 4, digitnum + 1):
        judgeS = int(S[begindigit:enddigit])
        if int(S[begindigit:enddigit]) % 2019 == 0:
            ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(str, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    S, W = LI()
    if S>W:
        print('safe')
    else:
        print('unsafe')

    
    return

# B


def B():
    A,B,C,D=LI()
    while(1):
        C=C-B
        if C<=0:
            print('Yes')
            break
        A=A-D
        if A<=0:
            print('No')
            break



    return

# C


def C():
    N=II()
    S=['i']*N
    for i in range(N):
        S[i]=input().rstrip()
    print(len(set(S)))

    return


def D():
    S=input().rstrip()
    ans=0
    for i in range(len(S)-3):
        for j in range(i+3+1,len(S)+1):
            if int(S[i:j])%2019 == 0:
                #print(i,j)
                ans+=1
    print(ans)
    return

# E


def E():
    N, K = LI()
    A = LI()
    F = LI()
    A.sort(reverse=True)
    F.sort()
    cost = []
    for i in range(len(N)):
        cost.append(A[i]*F[i])

    a = F[cost.index(max(cost))]

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    N = len(S)

    pass


# Solve
if __name__ == '__main__':

    D()

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

for x in num_list:
    p += mul2019(x)
print(p)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    S = input()
    len_S = len(S)
    counter = 0
    for i in range(199998):
        multiple = str(2019*i)
        len_m = len(multiple)
        for j in range(len_S - len_m + 1):
            if S[j:j+len_m] == multiple:
                counter += 1
    print(counter)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
digit_sum_mod3 = 0
start = 0

while start <= n-4:
  end = start + 4
  while end <= n:
    if end == start + 4:
      for i in range(4):
        index = start + i
        digit_sum_mod3 += int(s[index])
        digit_sum_mod3 %= 3
    if digit_sum_mod3 == 0:
      if int(s[start:end]) % 2019 == 0:
        ans += 1
    if end != n:
      digit_sum_mod3 += (int(s[end]) % 3)
      digit_sum_mod3 %= 3
    end += 1
  digit_sum_mod3 = 0
  start += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
x=1
ans=0
for i in range(len(S)-3):
    j=4
    while i+j <= len(S):
        if int(S[i:i+j])%2019==0:
            ans+=1
            j+=4
        else:
            j+=1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
L=list(S)
length=len(L)

def cal(i):
	total=0
	y=L[i]
	for j in range(i+1,length):
		x=int(str(y)+L[j])
		if x%2019==0:
			total+=1
			y=x
		else:
			y=x
	return total
    

Total=0
for i in range(0,length-3):
	Total+=cal(i)

print(Total)

Submission status: Time Limit Exceeded

Solution code:
import itertools

S = input()

def main():
    global S

    def main0(acc, s):
        for i in range(4, len(s)+1):
            a = int(s[0:i])
            if a < 2019:
                continue
            if a % 2019 == 0:
                acc += 1

        s = s[1:]
        if len(s) == 0:
            return acc
        else:
            return main0(acc, s)

    return main0(0, S)

print(main())

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 2019
m = 999999
#print(m / 2019)
#print(mod * 495)

#print(n)

l = 0
r = 4
ans = 0
while l < n - 3:
    while r <= n:
        #print(l+1,r+1,s[l:r])
        num = int(s[l:r])
        m = num % mod
        if m == 0:
            ans += 1
            r += 4
        else:
            r += 5 - len(str((num*10)%mod))
    l += 1
    r = l + 4

print(ans)

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:
mods_count = [0] * 2019

mod = 2019
ans = 0
S = input()
for s in S:
    num = int(s)
    new = [0] * 2019
    for i in range(2019):
        index = i + num
        count = mods_count[i]
        new[index % 2019] += count
    new[num] += 1

    ans += new[0]
    nexts = [0] * 2019
    for i in range(2019):
        index = i * 10
        count = new[i]
        nexts[index % 2019] += count

    mods_count = nexts

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline().rstrip
    s = input()
    d = 0
    flag = False
    for i in range((len(s)-3)):
        for j in range(i+3,len(s)):
            m = int(s[i:j+1])
            if m % 2019 == 0:
                d+= 1

    print(d)

resolve()

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 the required count 
    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()
LS=len(S)
Comb=0
MEMO=[]
if LS<4:
	print(0)
else:
	for i in range(LS-3):
		for j in range(i+4,LS+1):
			s=int(S[i:j])
			if s in MEMO or s%2019==0:
				Comb+=1
				MEMO.append(s)
	print(Comb)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

S = read_str()
l = len(S)

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

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

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
str=input()
gap_len=4
flag=0
count=0
if (len(str)==4):
    if(int(str)%2019==0):
        count+=1
for gap_len in range(4,len(str)):
    for i in list(range(len(str)-gap_len+1)):
        sub_str=str[flag:flag+gap_len]
        num=int(sub_str)
        if(num%2019==0):
            count+=1
        flag+=1
    flag=0
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num = str(N)
list_num = list(num)
list_num = [int(s) for s in list_num]
s=len(list_num)
ans=0
for i in range(4,s+2):
    for u in range(1,s-i+2):#hajimenobanngou
        a=int("".join((map(str,list_num[u-1:u+i-1]))))
        if  a%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
    
def print_ans(S):
    """Test Case
    >>> print_ans('1817181712114')
    3
    >>> print_ans('14282668646')
    2
    >>> print_ans('2119')
    0
    """
    target_list = []
    itr = 2019
    for i in range(1, 20001):
        tmp = i * itr
        if tmp > int(S):
            break
        elif '0' in list([s for s in str(tmp)]):
            continue
        else:
            target_list.append(tmp)
    ans = 0
    if len(S) <= 3:
        print(0)
    else:
        for i in range(len(S)-2):
            for j in range(i + 2, len(S)):
                tmp = S[i:j+1]
                if int(tmp) in target_list:
                    ans = ans + 1
        print(ans)
            
            

if __name__ == '__main__':
    S = input().rstrip()
    print_ans(S)

Submission status: Time Limit Exceeded

Solution code:
s = input()

n = len(s)

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

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

c=0
d=0
def check2019(S, n):
    global c
    global d
    s = int(S)
    if s%2019 ==0:
        c +=1
        if n ==2:
            d =1
    else:
        pass
    if s>10000:
        if n ==0:
            return check2019(S[1:],1), check2019(S[:-1], 0)
        else:
            return check2019(S[1:],2)
    else:
        return 0
S = input()


if len(S) >= 4:
    check2019(S, 0)
else:
    pass
print(c-d)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 21:27:49 2020

@author: arute
"""


from sys import stdin

import time
import numpy as np
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def toint(data):
    out = ""
    for d in data:
        out += str(d)
    return int(out)
############################################

# read data for n sequences.
temp = stdin.readline().split()
N = str(temp[0])

# 1817181712114
data = []
for i in range(len(N)):
    data.append(str(N)[i])

count = 0
for i in range(len(data)-3):
    for j in range(len(data)-3):
        if not i+j+3>=len(data):
            d = data[i : i+j+4]
            o = toint(d)
            if o%2019==0:
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = input()
nagasa = len(N)
count = 0
for a in range(1, nagasa+1):
    for b in range(a+1, nagasa+2):
        c = 0
        keta = b - a + 1
        if keta < 4:
            continue
        for k in range(1,keta):
            c += int(N[a - 2 + k]) * 10 ** (keta-k-1)
        if c % 2019 == 0  and c != 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools]
s = input()
n = len(s)
c = 0
for i in range(n-3):
    for j in range(3+i,n):
        num = int(s[i:j+1])
        if num % 2019 == 0:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = list(input())

ans = 0
for left in range(len(n)):
    for right in range(left+4,len(n)+1):
        temp = n[left:right]
        temp2 = 0
        cou = len(temp)
        for ele in temp:
          base = 10 ** (cou-1)
          temp2 += int(ele) * base
          cou -= 1
        
        if temp2%2019 == 0:
          ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

S = deque(input())
s = []
count = 0
for i in range(len(S)):
    s.append(S.popleft())
    d1 = int("".join(map(str, s)))
    if not S:
        pass
    else:
        d2 = int("".join(map(str, S)))

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

    for j in range(1, len(s)):
        d3 = int("".join(map(str, s[j:])))
        if d3%2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
a=input()

#b=int(a)

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
#dp[i][j]...i番目終わりまでで余りがj
dp=[[0]*2019 for i in range(len(S))]
count=0
for i in range(len(S)):
  dp[i][int(S[i])]+=1
  for j in range(2019):
    dp[i][(10*j+int(S[i]))%2019]+=dp[i-1][j]
  count+=dp[i][0]
#print(dp[len(S)-1][0])
print(count)

Submission status: Time Limit Exceeded

Solution code:
A =str(input())


N = int(len(A))

S = 0

for i in range(N):
  
  for j in range(N):
      
      if i >= j:
          continue
      
      x = (A[i:j+1])
      
      
      
      y = int(x)
      
      if y % 2019 == 0:
            S += 1

print(int(S))

Submission status: Time Limit Exceeded

Solution code:
S = input()

cnt = 0
memo_true = set()
memo_false = set()

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

Submission status: Time Limit Exceeded

Solution code:
import sys

S = input()
N = len(S)
if N < 5:
  print(0)
  sys.exit()
ans = 0
for i in range(N-4):
  t = int(S[i])
  for j in range(i+1, N):
    t = (t * 10 + int(S[j])) % 2019
    if t == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = len(S)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

s=input()
n=len(s)
dd = defaultdict(int)
q = deque()
if n<4:
    print(0)
    exit()
ans=0
for i in range(4):
    q.append(s[i])
if(int(''.join(q))%2019)==0:
    ans+=1

for i in range(0, n-3):
    for j in range(5, n+1, 3):
        if i+j<n+1:
            dd[(i,i+j)]+=1
            if(int(s[i:i+j])%2019==0) and dd[(i,i+j)]==1:
                ans+=1
                i=i+j
                break
            if j>n-4:
                for k in range(3):
                    if i+j+k<n:
                        dd[(i,i+j+k)]+=1
                        if int(s[i:i+j+k])%2019==0 and dd[(i,i+j+k)]==1:
                            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = [0] * (2019+1)

tmp = ""
for i in range(1, len(S)+1):
    tmp = S[-i] + str(tmp)
    mod[int(tmp) % 2019] += 1

ans = mod[0]
for i in range(1, 2020):
    if mod[i] >= 2:
        ans += (mod[i] * (mod[i]-1)) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def do():
    s=str(input())
    count=[0]*2019
    ans=0
    for i in range(len(s)):
        count_t=[0]*2019
        count_t[int(s[i])]+=1
        for k in range(2019):
            t=(k*10+int(s[i]))%2019
            count_t[k]-=count[k]
            count_t[t]+=count[k]
            if t==0:
                ans+=count[k]
        #print(count[0:20])
        #print(count_t[0:20])
        count=list(map(lambda x,y: x+y, count, count_t ))
    print(ans)
                
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
A=0
b=list(str(a))
c=int(len(b))
for i in range(c-3):
    for j in range(4,c+1-i):
        d=b[i:j+i]
        pg = ''.join(d)
        if int(pg)%2019==0:
            A+=1
print(A)

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

s = ns()[::-1]
b = [0]
for i in range(1,len(s)+1):
    b.append(int(s[:i][::-1])%2019)

import collections

c = collections.Counter(b)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fact
import math
import sys
import itertools
import numpy as np
from collections import Counter
import datetime


#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(range(n),r))



def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1):
	cf=[]
	for i in range(2,math.sqrt(x1)+1):
		if x1 % i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)

# 素因数分解
def factorization(n):
	tmp=n
	count=0
	for i in range(2,int(n**0.5)+2):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
				cnt+=1
				tmp//=i
			count+=1
	if tmp!=1:
		count+=1

	return count
			




s=str(input())
# combi=combinations(int(len(s)),2)
count=0
# for i in combi:
# 	start=i[0]
# 	end=i[1]
# 	num=int("".join(s[start:end+1]))
# 	if num%2019==0:
# 		count+=1
# 		print(start,end)
# print(count)
length=len(s)
for i in range(length):
	start=i
	if length-start<3:
		break
	for j in range(i+1,length):
		end=j
		if end-start<3:
			continue
		else:
			num=int(s[start:end+1])
			if num%2019==0:
				count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

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

Submission status: Time Limit Exceeded

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

for i in range(5,l+1):
    for j in range(0,l-i+1):
        ss=s[j:j+i]
        ss_n=int(ss)
        if ss_n%3==0:
            if ss_n%673==0:
                k+=1

print(k)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
##D - Multiple of 2019
S = str(input())
rc = 0
for i in range(len(S) - 4):
    for j in range(4 + i, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            rc += 1            
print(rc)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = []
for i in range(0, N+1):
    for j in range(i, N+1):
        b = 0
        for k in range(i, j):
            b = b * 10 + h[k]
        a.append(b)
c = 0
for m in range(0, len(a)):
    if a[m] != 0 and a[m] % 2019 == 0:
        c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
S = input()
l = len(S)
ans = 0
for i in range(l-3):
  for j in range(i+3,l):
    s = S[i:j+1]
    if sum([int(c) for c in s]) % 3 == 0:
        if int(s) % 2019 == 0:
            #print(s)
            ans += 1
            #print("ok")
            break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    s = S()
    n = len(s)
    c=0
    for i in range(n):
        for j in range(i+3,n):
            x = s[i:j+1]
            z = int(x)
            if z>=2019:
                if int(x)%2019==0:
                    c+=1
    print(c)
    # numMultiples = 0
    # seenRemainders = [set() for i in range(n)]
    # for i in range(1,n):
    #     remainder = 0
    #     prefixesFound = 0
    #     for j in range(i,n):
    #         z=10 * remainder + int(s[j])
    #         remainder = (10 * remainder + int(s[j])) % 2019
    #         if remainder in seenRemainders[j]:
    #             break
    #         seenRemainders[j].add(remainder)
    #         if remainder == 0:
    #             print(z)
    #             prefixesFound+=1
    #     numMultiples += (prefixesFound * (prefixesFound + 1))// 2
    # print(numMultiples)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    # start_time = time.perf_counter()
    s = input()
    cnt = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if sum(int(x) for x in list(s[i:j])) % 3 != 0:
                continue
            n = int(s[i:j])
            if n % 673 == 0:
                cnt += 1
    print(cnt)
    # print("perf_counter = {:.7f}".format(time.perf_counter() - start_time))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
tmp = 0
result = 0
for p in range(0, len(S) - 3):
    for q in range(p + 3, len(S)):
        if q == p + 3:
            tmp = int(''.join(S[p:q + 1]))
        else:
            tmp = tmp * 10 + int(S[q])
        if tmp % 2019 == 0:
            result += 1
            
print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(list)
for i in range(len(s)):
    cum[i+1]=cum[i]+int(s[i])
for i in range(len(s)+1):
    d[cum[i]%3].append(i)
ret = 0
#print(cum,d)
for l in d.values():
    #print(l)
    n = len(l)
    can = [[l[i],l[j]] for i in range(n) for j in range(i,n) if l[j] > l[i]+3]
    #print(can)
    #print([[i,j,int(s[i:j])] for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0])
    #print([1 for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0])
    ret += sum(1 for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
dict = {}
cnt = 0
for i in range(len(S)-3):
    val = int(S[i]) + int(S[i+1]) + int(S[i+2])
    for j in range(i+3, len(S)):
        val += int(S[j])
        if S[i:j+1] in dict:
            dict[S[i:j+1]] += 1
        else:
            if val%3 == 0:
                dict[S[i:j+1]] = 1


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

'''

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()
l = len(S)
ans = 0

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