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

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8

S = input() #文字列型で受け取る
N = len(S)

remainder = [0] * 2019

for i in range(N):
    #print(S[i:], int(S[i:])%2019)
    remainder[int(S[i:])%2019]+= 1
remainder[0] += 1

answer = 0
for i in range(2019):
    p = remainder[i]
    answer += p*(p-1)/2
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10

for i in range(2019):
  ans += mod_list[i] * (mod_list[i] - 1) // 2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8

S = input() #文字列型で受け取る
N = len(S)

remainder = [0] * 2019

for i in range(N):
    #print(S[i:], int(S[i:])%2019)
    remainder[int(S[i:])%2019]+= 1
remainder[0] += 1

answer = 0
for i in range(2019):
    answer += int(remainder[i] * (remainder[i]-1) / 2)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
s = input()
counts = [0]*2019
counts[0] += 1
num = 0
digit = 0
for c in reversed(s):
    num += int(c) * 10**digit
    counts[num % 2019] += 1
    digit += 1
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
s=s[::-1]
#print(s) #並び替え
n=len(s)
 
count=[0]*2019
count[0]=1
num,d=0,1
 
for i in s:
  num+=int(i)*d
  #print(d)
  #print(i,num)
  num%=2019
  d*=10
  #print(num)
  #d%=2019
  count[num]+=1
  
ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


if __name__ == "__main__":
    #main()

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = [0 for i in range(2019)]
    mod_arr[0] += 1
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i>0: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        else:   mod = _%2019
        mod_arr[mod]+=1
    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
s=s[::-1] #並び替え
#print(s) 
n=len(s)
 
count=[0]*2019 
count[0]=1
num,d=0,1
 
for i in s:
  num+=int(i)*d #累積を求める
  a=num
  a=num%2019 #余りを求める
  d*=10
  count[a]+=1 #indexがmodの値
  
ans=0
for i in count: #何通りか
  ans+=i*(i-1)//2 # ex)3つあったら3通り、4つあったら6通り
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
ans=0
for i in range(4,len(s)+1):
  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:
from sys import stdin
from collections import OrderedDict

def 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
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = OrderedDict()
    for i in range(2019):
        mod_arr[i] = 0
    mod_arr[0] += 1
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i>0: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        else:   mod = _%2019
        mod_arr[mod]+=1
    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def 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
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = {}
    for i in range(2019):
        mod_arr[i] = 0
    mod_arr[0] += 1
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i>0: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        else:   mod = _%2019
        mod_arr[mod]+=1
    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()

Submission status: Time Limit Exceeded

Solution code:

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def 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
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = {}
    for i in range(2019):
        mod_arr[i] = 0
    mod_arr[0] += 1
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i>0: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        else:   mod = _%2019
        mod_arr[mod]+=1
    for value in mod_arr.values():
        if value>1:
            cnt += value*(value-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
d = 1
num = 0
ans = 0
mod_list = [0] * 2019
mod_list[0] = 1

for char in s:
    num += int(char) * d
    mod_list[num % 2019] += 1
    d *= 10

for i in range(2019):
    ans += mod_list[i] * (mod_list[i] - 1) //2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import Counter


def 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
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = [0]
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i==0: mod = _%2019
        else: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        mod_arr.append(mod)
    mod_count = Counter(mod_arr)
    for value in mod_count.values():
        if value>1:
            cnt += value*(value-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1
for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10 % 2019
    ans += cnt[total]
    cnt[total] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import Counter


def 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
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = []
    for i in range(0,len_S+1):
        if len(S[len_S-i:])==0: 
            mod_arr.append(0)
        else:
            _ = int(S[len_S-i:])
            if i==1: mod = _%2019
            else: mod = (mod+int(S[len_S-i])*10**(i-1))%2019
            mod_arr.append(mod)
    mod_count = Counter(mod_arr)
    for value in mod_count.values():
        if value>1:
            cnt += value*(value-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
mod = [1] + [0 for _ in range(2019)]
ml = [0 for _ in range(l + 1)]
ans = 0

tmp = 0
for idx, degit in enumerate(s[::-1]):
    m = (int(degit) * (10 ** idx) + tmp) % 2019
    tmp = m
    ans += mod[m]
    mod[m] += 1

print(ans)

Submission status: Time Limit Exceeded

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

cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in s:
    total += int(i) * x
    total %= 2019
    x *= 10 % 2019
    ans += cnt[total]
    cnt[total] += 1

print(ans)

Submission status: Time Limit Exceeded

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

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10 % 2019
    ans += cnt[total]
    cnt[total] += 1

print(ans)

Submission status: Time Limit Exceeded

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

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10
    ans += cnt[total]
    cnt[total] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
mod = [0 for _ in range(2019)]
ml = [0 for _ in range(l + 1)]


for idx, degit in enumerate(reversed(s)):
    m = (int(degit) * (10 ** idx) + ml[l-idx]) % 2019
    ml[l-idx-1] = m
    mod[m] += 1

ans = 0
for idx, i in enumerate(mod):
    if i >= 0:
        ans += (i * (i - 1)) / 2

ans += mod[0]
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:


N = input()

def mod(power, d):
    a = d
    for i in range(power):
        a = a * 10
        a = a % 2019
    return a

T = {}
for j in range(len(N), -1, -1):
    if j == len(N):
        T[j] = 0
    else:
        T[j] = (T[j + 1] + mod(len(N) - j - 1,  int(N[j]))) % 2019
result = 0
for m in range(2019):
    a = 0
    for k, v in T.items():
        if v == m:
            a += 1
    if a >= 2:
        result += (a - 1) * a // 2
print(result)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
ans = [0]*2019
ans[0] = 1
num =0
t= 0
d = 1
for i in S:
    num += int(i) * d
    num %= 2019
    d *= 10
    ans[num] += 1

for c in ans:
    t += c * (c-1) //2

print(t)

Submission status: Time Limit Exceeded

Solution code:
S = input()
lmax = len(S)
modulo = list([0]*2019)
if(len(S) < 4):
    print(0)
    exit()
for i in range(lmax):
    s = int(S[i:])%2019
    modulo[s] += 1
ans = sum(list(map(lambda x: x*(x-1)//2, modulo)))+modulo[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main4():
	S = input()
	l = len(S)
	n = 0
	for i in range(l): #1文字目
		for j in range(i+4, l+1):
			A = S[i:j]
			if int(A)%2019 ==0:
				n += 1
	print(n)
				
				
main4()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    r = [0]*len(s)
    r[0] = int(s[-1])
    for i in range(1,len(s)):
        temp = (int(s[-(1+i)])*10**i) % 2019 
        r[i] = (temp+r[i-1])%2019
 
    ans = 0
    cts = [0]*2019
    for i in r:
        ans+=cts[i]
        cts[i]+=1
    
    if cts[0]>0:
        ans+=1
 
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main4():
	S = input()
	l = len(S)
	n = 0
	for i in range(l): #1文字目
		for j in range(i+1, l+1):
			A = S[i:j]
			if int(A)%2019 ==0:
				n += 1
	print(n)
				
				
main4()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    r = [0]*len(s)
    r[0] = int(s[-1])
    temp = r[0]
    for i in range(1,len(s)):
        r[i] = (int(s[-(1+i)])*10**i+ temp) % 2019
        temp = r[i]
    
    ans = 0
    cts = [0]*2019
    for i in r:
        ans+=cts[i]
        cts[i]+=1
    
    if cts[0]>0:
        ans+=1

    print(ans)
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def my_trim(target,i):
    return target[len(target)-i:]

target = input()
rem = defaultdict(list)
for i in range(1,len(target)+1):
    rem[int(my_trim(target,i))%2019].append(int(my_trim(target,i)))
answer = 0
for i in range(2019):
    answer += int((len(rem[i])*(len(rem[i])-1))/2)
answer += len(rem[0])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S=input()[::-1]
l=len(S)
t=0
p=0

ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    ss[p]+=1

for c in ss:
    t+=c*(c-1)//2
print(t)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    r = [0]*len(s)
    r[0] = int(s[-1])
    for i in range(1,len(s)):
        r[i] = (int(s[-(1+i)])*10**i+ r[i-1]) % 2019
    
    ans = 0
    cts = [0]*2019
    for i in r:
        ans+=cts[i]
        cts[i]+=1
    
    if cts[0]>0:
        ans+=1
        
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import collections
S=input()[::-1]
l=len(S)
t=0
p=0

ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    ss[p]+=1

for c in ss:
    t+=c*(c-1)//2
print(t)

Submission status: Time Limit Exceeded

Solution code:
import collections
S=input()
l=len(S)
t=0
p=0
m=[]
ss=[0]*2019
ss[0]=1
for i in range(l):
    p=(p+int(S[i])*(10**(l-1-i)))%2019
    ss[p]+=1
for c in ss:
    t+=c*(c-1)//2
print(t)

Submission status: Time Limit Exceeded

Solution code:
import collections
S=input()
l=len(S)
t=0
p=0
m=[]
ss=[0]
for i in range(l):
    m.append(int(S[i])*(10**(l-1-i))%2019)
    ss.append((ss[i]+m[i])%2019)

k=collections.Counter(ss)

for i in k.values():
    t+=(i-1)
print(t)

Submission status: Time Limit Exceeded

Solution code:
import collections as c
s = input()
r = [0]*len(s)
r[0] = int(s[-1])
for i in range(1,len(s)):
  r[i] = (int(s[-(1+i)])*10**i+ r[i-1]) % 2019

rc = c.Counter(r)
rl = list(rc.values())
sum = 0
for i in rl:
  sum += int(i*(i-1)/2)

if 0 in rc:
	sum+=1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import collections
S=input()
l=len(S)
t=0
p=0
m=[]
ss=[0]
for i in range(l):
    m.append(int(S[i])*(10**(l-1-i))%2019)
    ss.append((ss[i]+m[i])%2019)

k=collections.Counter(ss)

for i in k.values():
    if i>1:
        t+=(i-1)
print(t)

Submission status: Time Limit Exceeded

Solution code:
import collections
S=input()
l=len(S)
t=0
p=0
m=[0] * l
ss=[0]*(l+1)
for i in range(l):
    m[i]=int(S[i])*(10**(l-1-i))%2019
    ss[i+1]=(ss[i]+m[i])%2019

k=collections.Counter(ss)

for i in k.values():
    if i>1:
        t+=(i-1)
print(t)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections as c
    s = input()
    r = [0]*len(s)
    r[0] = int(s[-1])
    for i in range(1,len(s)):
        r[i] = (int(s[-(1+i)])*10**i+ r[i-1]) % 2019
    
    rc = c.Counter(r)
    rl = list(rc.values())
    sum = 0
    for i in rl:
        sum += int(i*(i-1)/2)

    if 0 in rc:
        sum+=1

    print(sum)

main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
l=len(S)
t=0
p=0
m=[0] * l

for i in range(l):
    m[i]=int(S[i])*(10**(l-1-i))%2019

for i in range(l-3):
    p=0
    for j in range(l-i):
        p=(p+m[i+j])%2019
        if p==0:
            t+=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
S=input()
l=len(S)
t=0
p=0
m=[0] * l

for i in range(l):
    m[i]=int(S[i])*(10**(l-1-i))%2019

for i in range(l):
    p=0
    for j in range(l-i):
        p=(p+m[i+j])%2019
        if p==0:
            t+=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
cnt = 0
keta = 1
for i in range(len(s)):
    cnt = (cnt + int(s[-(i+1)]) * keta) % 2019
    arr.append(cnt)
    keta *=10

for i in range(len(arr)):
    amari[arr[i]] +=1    
    
for i in amari:
    ans = ans + i * (i-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

target = int(input())
rem = defaultdict(list)
for i in range(1,len(str(target))+1):
    rem[(target%(10**i))%2019].append(target%(10**i))
answer = 0
for i in range(2019):
    answer += int((len(rem[i])*(len(rem[i])-1))/2)
answer += len(rem[0])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

target = int(input())
rem = defaultdict(list)
for i in range(1,len(str(target))+1):
    rem[(target%(10**i))%2019].append(target%(10**i))
answer = 0
for i in range(2019):
    answer += int((len(rem[i])*(len(rem[i])-1))/2)
answer += len(rem[0])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
for i in range(1, l+1):
    res += int(s[-i]) * 10 ** (i-1)
    res %= 2019
    count[res] += 1
print(int(sum([m*(m-1)/2 for m in count])))

Submission status: Time Limit Exceeded

Solution code:
s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
for i in range(len(s)):
    arr.append(int(s[-(i+1):])%2019)

for i in range(len(arr)):
    amari[arr[i]] +=1    
    
for i in amari:
    ans = ans + i * (i-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10

ans = 0

for i in num:
    ans += i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in range(n):
    number += int(s[i])*d
    num[number%2019] += 1
    d *= 10

ans = 0

for i in num:
    ans += i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  k = (int(S[i])%p) * (pow(10,N-i-1)%p)
  k %= p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = cnt[0]
for i in range(1,p):
  if cnt[i] > 0:
    ans += cnt[i]-1

print(ans)

Submission status: Time Limit Exceeded

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

num = [0]*2019
num[0] = 1

for i in range(n):
    number = int(s[i:])
    num[number%2019] += 1

ans = 0

for i in num:
    ans += i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

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

num = [0]
ans = 0

for i in range(n):
    a = int(s[-i-1:])
    a = a% 2019
    num.append(a)
    b = num[:-1]
    ans += b.count(a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  
  k = (int(S[i])*pow(10,N-i-1))%p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = cnt[0]
for i in range(1,p):
  if cnt[i] > 0:
    ans += cnt[i]-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  k = (int(S[i])*10**(N-i-1))%p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = cnt[0]
for i in range(1,p):
  if cnt[i] > 0:
    ans += cnt[i]-1

print(ans)

Submission status: Time Limit Exceeded

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

num = []

for i in range(n):
    number = int(s[i:])
    num.append(number%2019)

num.append(0)

ans = 0

for i in range(len(num)):
    a = num[i]
    b = num[i+1:]
    ans += b.count(a)

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    # 入力
    st = input()

    if len(st) < 4:
        print(0)
        return

    cnt = 0
    for l in range(4, len(st)+1):
        for idx in range(len(st) + 1 - l):
            target_st = st[idx:idx+l]
            if int(target_st) % 2019 == 0:
                cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

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

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    U = [0]
    dic = {0:1} # value:count
    ans = 0
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (10**(rev_i+1))
        u = V[rev_i+1] % K
        if u in dic:
            dic[u] += 1
            cnt = dic[u]
            ans -= (cnt-1) * (cnt-2) // 2
            ans += cnt * (cnt-1) // 2
        else:
            dic[u] = 1
            # U.append(u)


    # for u in U:
    #     u_count = dic[u]
    #     ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (10**(rev_i+1))
        # print(V)

    dic = {} # value:count
    U = []
    for v in V:
        u = v % K
        if u in dic:
            dic[u] += 1
        else:
            dic[u] = 1
            U.append(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (10**(rev_i+1))
        # print(V)

    dic = {} # value:count
    U = []
    for v in V:
        u = v % K
        if u in dic:
            dic[u] += 1
        else:
            dic[u] = 1
            U.append(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n = input()
countArray = [0] * 2019
count = 0
countArray[0] += 1
nums=0
for i in range(len(n))[::-1]:
    nums = nums + int(n[len(n)-1-i])*pow(10,i)
    countArray[nums%2019]+=1

for i in countArray:
    count += (i * (i - 1)) / 2
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
s = input()
 
arr = [0]
amari = [0 for i in range(2019)]
ans = 0
for i in range(len(s)):
    arr.append(int(s[-(i+1):])%2019)
 
for i in range(len(arr)):
    amari[arr[i]] +=1
 
for i in amari:
    ans += i * (i-1) // 2
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
 
arr = [0]
amari = [0 for i in range(2019)]
ans = 0
for i in range(len(s)):
    arr.append(int(s[-(i+1):])%2019)
 
for i in range(len(arr)):
    amari[arr[i]] +=1
 
for i in amari:
    ans += i * (i-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = input()
countArray = [0] * 2019
count = 0
countArray[0] +=1
for i in range(len(n)):
    countArray[int(n[-i-1:])%2019]+=1

for i in countArray:
    count += (i * (i - 1)) / 2
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
s = input()

mod = [1] + [0]*2018
t = 0
a = 0
n = len(s)
s = s[::-1]
for i in range(n):
    t += int(s[i]) * (10 ** a)
    a += 1
    mod[t%2019] += 1
    #print(t,t%2019)
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
kake = 1
ret = 0
len_s = len(S)
for i in reversed(S) :
	p_amari = ( int(i) * kake + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
	kake *= 10
print(int(ret))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

S = str(sys.stdin.read().rstrip())

dp = [0]*2019
ans = 0
for s in S:
    new_dp = [0]*2019
    new_dp[int(s)] += 1
    for i in range(2019):
        new_dp[(i*10+int(s))%2019] += dp[i]
    dp = new_dp
    ans += dp[0]

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# multiple
line = input()
ln = 0
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*10**(i-1))%2019)%2019
    counts[ti1] += 1
    ln = ti1
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))

Submission status: Time Limit Exceeded

Solution code:
# multiple
line = input()
ln = [0]
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln[-1] +(int(line[-1*i])*10**(i-1))%2019)%2019
    counts[ti1] += 1
    ln.append(ti1)
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
S = input()
#1817181712114
N = len(S)
k = 0
for i in range(N):
  for j in range(i+1, N+1):
    if j-i >3:
      if int(S[i:j]) % 2019 == 0:
        k = k + 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
s = input()
dic = {}
for i in range(2019):
  dic[i] = 0
dic[0] = 1
m = 0
for j in range(1, len(s)+1):
  m = int(s[-j]) * 10**(j-1) + m
  m %= 2019
  dic[m] += 1
ans = 0
for v in dic.values():
  ans += v*(v-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
S = input()
#1817181712114
N = len(S)
k = 0
for i in range(N):
  for j in range(i+1, N+1):
    #print(S[i:j])
    if int(S[i:j]) % 2019 == 0:
      k = k + 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
kake = 1
ret = 0
len_s = len(S)
for i in range(len_s) :
	p_amari = ( int(S[len_s-1-i]) * kake + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
	kake *= 10
print(int(ret))

Submission status: Time Limit Exceeded

Solution code:
S = input()

count = 0
mod_check = [0] * 2019
mod_check[0] = 1
check_S = 0
for i in reversed(S):
    check_S += int(i) * (10 ** count)
    mod = check_S % 2019
    # mod_check.setdefault(mod, 0)
    mod_check[mod] += 1
    count += 1
mod_match = 0
for x in mod_check:
    mod_match += x * (x - 1) // 2
print(mod_match)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
kake = 1
ret = 0
for i in range(len(S)) :
	p_amari = ( int(S[len(S)-1-i]) * kake + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
	kake *= 10
print(int(ret))

Submission status: Time Limit Exceeded

Solution code:
S = input()

count = 0
mod_check = {}
mod_check[0] = 1
check_S = 0
for i in reversed(S):
    check_S += int(i) * (10 ** count)
    mod = check_S % 2019
    mod_check.setdefault(mod, 0)
    mod_check[mod] += 1
    count += 1
mod_match = 0
for x in mod_check.values():
    mod_match += x * (x - 1) // 2
print(mod_match)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
kake = 1
for i in range(len(S)) :
	p_amari = ( int(S[len(S)-1-i]) * kake + p_amari ) % 2019
	ls[p_amari] += 1
	kake *= 10
ret = 0
for i in range(2019) :
	n = ls[i]
	if n == 0 :
		continue
	ret += n * (n -1 ) / 2
print(int(ret))