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:
n = input()
all_int = list()
ans = 0
for i in range(len(n)):
    for j in range(i+1,len(n)+1):
        s = n[i:j]
        if(int(s) > 0 and len(s)>=4 and int(s)%2019 == 0):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
P = [0] * (len(S)+1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
P = [0 for _ in range(len(S)+1)]
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

A = [0] * 2019
for p in P:
    A[p] += 1

ans = 0
for a in A:
    ans += a*(a-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
P = [0 for _ in range(len(S)+1)]
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

A = [0 for _ in range(2019)]
for p in P:
    A[p] += 1

ans = sum(list(map(lambda n: n*(n-1)//2, A)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        a = int(S[i:j])
        ans += a%2019 == 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s = input()

ls = len(s)
t = [0]
for i in range(1, ls+1):
    t.append((int(s[ls-i:ls:])) % 2019)
c = Counter(t)
k = list(c.keys())
ans = 0
for i in k:
    ans += c[i]*(c[i]-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(len(s), 3, -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 collections import defaultdict

S = input()

d = defaultdict(int)

d[0] += 1

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

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()

d = defaultdict(int)

d[0] += 1

for i in range(len(S)):
    mod = int(S[i:]) % 2019
    d[mod] += 1

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    # s += int(S[i]) * ((10 ** (len(S) - 1 - i)) % 2019)
    # s %= 2019
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
for i in range(1, len(S) + 1):
    s += (int(S[-i]) * ((10 ** (i - 1)) % 2019))
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
for i in range(1, len(S) + 1):
    s += (int(S[-i]) * (10 ** (i - 1)))
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
for i in range(1, len(S) + 1):
    s += int(S[-i]) * (10 ** (i - 1))
    # print(s)
    div.append(s % 2019)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += combinations_count(l, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
for i in range(1, len(S) + 1):
    s = int(S[-i:])
    div.append(s % 2019)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += combinations_count(l, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D
from numba import jit
from itertools import combinations
@jit
def main(S):
    comb=list(combinations(range(len(S)+1),2))
    count=0
    for i in comb:
        i_0=i[0]
        i_1=i[1]
        if int(S[i_0:i_1])%2019==0:
            count+=1
    return count
S=input()
print(main(S))

Submission status: Time Limit Exceeded

Solution code:
#D
from numba import jit
from numba import prange
@jit(parallel=True)
def solve(S):
    len_S=len(S)
    count=0
    for i in prange(len_S-3):
        for j in prange(i+3,len_S+1):
            if int(S[i:j])%2019==0:
                count+=1
    return count
print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
#D
from numba import jit
@jit
def solve(S):
    len_S=len(S)
    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
    return count
print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
#D
from itertools import combinations
from sys import stdin
def main():
    readline = stdin.readline
    S=input()
    len_S=len(S)

    if len_S <4:
        print(0)

    else:
        comb=list(combinations(range(len_S+1),2))
        count=0
        for i in comb:
            i_0=i[0]
            i_1=i[1]
            if int(S[i_0:i_1])%2019==0:
                count+=1
        print(count)
main()

Submission status: Time Limit Exceeded

Solution code:
#D
from itertools import combinations
from sys import stdin
def main():
    readline = stdin.readline
    S=input()
    len_S=len(S)

    if len_S <4:
        print(0)

    else:
        comb=list(combinations(range(len_S+1),2))
        count=0
        for i in comb:
            i_0=i[0]
            i_1=i[1]
            if int(S[i_0:i_1])%2019==0:
                count+=1
        print(count)  
main()

Submission status: Time Limit Exceeded

Solution code:
#D
from itertools import combinations

S=input()
len_S=len(S)

if len_S <4:
    print(0)

else:
    comb=list(combinations(range(len_S+1),2))
    count=0
    for i in comb:
        i_0=i[0]
        i_1=i[1]
        if int(S[i_0:i_1])%2019==0:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#D
from itertools import combinations

S=input()
len_S=len(S)
comb=list(combinations(range(len_S+1),2))

count=0
for i in comb:
    i_0=i[0]
    i_1=i[1]
    if int(S[i_0:i_1])%2019==0:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#D
S=input()
len_S=len(S)
if len_S <4:
    print(0)
else:
    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:
#D
S=input()
 
count=0
for i in range(len(S)):
    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:
#D
S=input()

count=0
for i in range(len(S)):
    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:
"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+pow(10,i)*int(S[i])%2019)%2019
    ans += memo[num]
    memo[num] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num += pow(10,i)*int(S[i])
    r = num%2019
    ans += memo[r]
    memo[r] += 1

print(ans)

Submission status: Time Limit Exceeded

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

counter = [0] * 2019
counter[0] = 1
T = 0
for i in range(N):
    T = ((10 ** i) * int(S[N - i - 1]) + T) % 2019
    counter[T] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    S = list(input())
    rem = [0 for _ in range(2019)]
    v = 0
    rem[0] += 1
    n_p = 0
    for i in range(len(S)-1, -1, -1):
        v = (10**n_p)*int(S[i]) + v
        v %= 2019
        rem[v] += 1
        n_p += 1
    ans = 0
    for r in rem:
        ans += r*(r-1)//2
    print(ans)
        



if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
s = input()
n = len(s)

mods = [0] * 2019
mods[0] = 1
for i in range(n):
    now = int(s[n-i-1:n])
    mods[now%2019] += 1

ans = 0
for i in range(2019):
    if mods[i] >= 2:
        ans += combinations_count(mods[i],2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(map(int, input()))
L = len(S)
mod = 2019
T = []
t = 0
p = 1
for i in range(L-1, -1, -1):
  t = (t + S[i] * p) % mod
  T.append(t)
  p = (p * 10) % mod
R = [T.count(t) for t in set(T)]
print(T.count(0) + sum([r * (r-1) // 2 for r in R]))

Submission status: Time Limit Exceeded

Solution code:
S = list(map(int, input()))
L = len(S)
mod = 2019
ans = 0
for i in range(L):
  a = 0
  j = i
  while j < L:
    a = (10 * a + S[j]) % mod
    if a == 0:
      ans += 1
    j += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

dp = [0]*len(s)
# dp[i]: sの左からi文字目以降を整数と見なした時の2019で割った余り
dp[len(s)-1] = int(s[len(s)-1])

reg = [0]*2020
# 余りを記録

for i in range(len(s)-2, -1, -1):
    dp[i] = ( dp[i+1] + int(s[i])*pow(10, len(s)-1-i) ) % 2019
    reg[dp[i]] += 1

ans = reg[0]
for i in range(2020):
    ans += reg[i] * (reg[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)-1, -1, -1):
    a[F(s, i)] += 1

ans = a[0]
for i in range(2020):
    ans += a[i] * (a[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)):
    a[F(s, i)] += 1

ans = a[0]
for i in range(2020):
    ans += a[i] * (a[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

s = input()

mod = 2019
n = len(s)
t = [0]*(n+1)
for i in range(1,n+1):
    t[i] = (t[i-1] + int(s[n-i]) * (10**(i-1) % mod)) % mod
# t[i-1] == t[j] mod2019　のとき、i番~j番目が2019の倍数
c = collections.Counter(t)
num = c.values()
ans = 0
for i in num:
    ans += i*(i-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
x = 0
if int(S) < 2019:
    pass
else:
    for i in range(len(S)-1):
        for j in range(i+1, len(S)+1):
            N = int(S[i:j])
            if N > 2019 and N % 2019 == 0:
                x += 1
print(x)

Submission status: Time Limit Exceeded

Solution code:
S = input()

cnt = 0
for i in range(len(S) - 4 + 1):
    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:
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)


INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict


def solve(S):
    N = len(S)

    v1 = [0] * (N+1)
    v1[0] = 0

    for i in range(N):
        v1[i+1] = v1[i] * 10 + int(S[i])

    counter = Counter()
    for i in range(N+1):
        u = v1[i] * pow(10,201900-i,2019) % 2019
        counter.add(u)

    
    ans = 0
    # print(counter.get_dict())
    for _,count in counter.get_dict().items():
        ans += count * (count-1) // 2
    
    print(ans)

    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = list((next(tokens)))  # type: int
    solve(S)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#2019 = 3*673
arr = list(str(input()))
lis = [int(s) for s in arr]
ans = 0
l = len(lis)
if l < 4:
  print(0)
  exit()
for i in range(0,l-3):
  per3 = (lis[i]+ lis[i+1] + lis[i+2])%3
  for j in range(i+3,l):
    per3 += lis[j]
    b = arr[i:j+1]
    a = int(''.join(b))
    if per3%3 == 0: 
      if a %673 == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
#coding = SJIS

s = str(input())
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding = SJIS

s = str(input())
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = (num + (10 ** i) * s_array[len_s - i - 1])
    mod_array[num%mod] += 1

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

print(int(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0]=0,1
for i in range(1,n+1):
  s+=int(S[-i])*(10**(i-1))
  dp[s%2019]+=1
for i in range(2019):
  m=dp[i]
  ans+=m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

x10=1
for j, i in enumerate(s):
  S[j+1]=(S[j]+(x10*int(i)))%p
  x10*=10
  ans[S[j+1]]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for j, i in enumerate(s):
  S[j+1]=(S[j]+(10**(j)*int(i)))%p
  ans[S[j+1]]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
p=2019
ans=[0]*p

x10=1
S=0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10%p
  ans[S]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for i in range(n):
  S[i+1]=(S[i]+(10**(i)*int(s[i]))%p)%p
  ans[S[i+1]]+=1

cnt=ans[0]
for i, a in enumerate(ans):
  cnt+=(a*(a-1))//2
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for i in range(n):
  S[i+1]=(S[i]+(10**(i)*int(s[i]))%p)%p
  ans[S[i+1]]+=1

cnt=ans[0]
for i, a in enumerate(ans):
  if i:
  	cnt+=(a*(a-1))//2
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for i in range(n):
  S[i+1]=(S[i]+(10**(i)*int(s[i])))%p
  ans[S[i+1]]+=1

cnt=ans[0]
for i, a in enumerate(ans):
  if i:
  	cnt+=(a*(a-1))//2
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(map(int, list(input())))
mod = 2019
lens = len(S)
mods = [0]*lens
cum = 0
for i in range(lens):
    s = S[-i-1]
    cum += s*(10**i)
    cum %= mod
    mods[i] = cum
mods += [0]
from collections import Counter
c = Counter(mods)

ans = 0
for num, cnt in c.most_common():
    if cnt<2:
        break
    ans += cnt*(cnt-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

S=list(input())
S=list(map(int,S))[::-1]


mod=[0]*2019
mod[0]+=1

ans=0
temp=0
for i in range(len(S)):
    temp+=S[i]*10**i
    temp%=2019
    ans+=mod[temp]
    mod[temp]+=1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=[int(x) for x in list(input())]
n=len(s)
dp = [0]*(n+1)
for i in reversed(range(n)):
  dp[i] = (dp[i+1] + s[i]*10**(n-i-1)) % 2019

x = [0]*2019
for i in range(n):
  x[dp[i]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
x = [0]*2019
for i in range(len(s)):
  x[int(s[i:])%2019] += 1

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

Submission status: Time Limit Exceeded

Solution code:
t = input()
s = list(t)
s = list(map(int,s))
n = len(s)
ls = [0]*(n+1)
cnt = 0
for i in range(n):
    ls[i+1] = ls[i] + s[i]
for j in range(n):
    for k in range(j+1,n+1):
        a = ls[k] - ls[j]
        if a % 3 == 0:
            if int(t[j:k]) % 673 == 0:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
n=len(s)
a=[0]*2019
a[0]=1
c,d=0,1
for i in s:
    c+=int(i)*d
    c%=2019
    d*=10
    # d%=2019
    a[c]+=1
ans=0
for i in a:
    ans+=i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
S=len(s)
cnt=0
for i in range(S):
    if i+3<=S:
        for j in range(4,S+1):
            if len(s)-i>=4:
                if i<j:
                    I=int(s[i:j])
                    # print("I=",I)
                    if I%2019==0:
                        cnt+=1
                        # print(i,j)
            else:
                break
    else:
        break
   

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
S=len(s)
cnt=0
for i in range(200000):
    if i+3<=S:
        for j in range(4,S+1):
            if len(s)-i>=4:
                if i<j:
                    I=int(s[i:j])
                    # print("I=",I)
                    if I%2019==0:
                        cnt+=1
                        # print(i,j)
            else:
                break
    else:
        break
   

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
S = input()
dict_amari = {}
count = 0

henkan = {i: [(10*j+i)%2019 for j in range(2019)] for i in range(1,10)}

def amari_new(dict_amari, s, henkan):
  dict_amari_new = {henkan[k] : v for k,v in dict_amari.items()}
  if s in dict_amari_new.keys():
    dict_amari_new[s] += 1
  else:
    dict_amari_new[s] = 1
  return dict_amari_new

for s in S:
  dict_amari = amari_new(dict_amari, int(s), henkan[int(s)])
  if 0 in dict_amari.keys():
    count += dict_amari[0]

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
d=[0]*2019
d[0]=1
j=1
ans=0
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  ans+=d[now]
  d[now]+=1
  j*=10
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
d=dict(zip(list(range(2019)),[0]*2019))
d[0]=1
j=1
ans=0
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  ans+=d[now]
  d[now]+=1
  j*=10
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
d=dict(zip(list(range(2019)),[0]*2019))
d[0]=1
j=1
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  d[now]+=1
  j*=10
ans=0
for _,i in d.items():
  ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
d=dict(zip(list(range(2019)),[0]*2019))
i=1
while i//10<=s:
  d[s%i%2019]+=1
  i*=10
ans=0
for _,i in d.items():
  ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
d=dict(zip(list(range(2019)),[0]*2019))
i=0
while 10**(i-1)<=s:
  d[s%10**i%2019]+=1
  i+=1
ans=0
for _,i in d.items():
  ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
d=dict(zip(list(range(2019)),[0]*2019))
for i in range(n):
  d[int(s[i:])%2019]+=1
ans=0
for _,i in d.items():
  ans+=i*(i-1)//2
ans+=d[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
l=list(input())
ans=0

for i in range(len(l)-3):
    for j in range(i+4,len(l)+1):
        attempt=l[i:j]
        a=int("".join(attempt))

        if a%2019==0:
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
S = S[::-1]
# 1桁のmod2019, 2桁の2019, ...
# 0桁のmod2019=0と定めると都合が良い
l = [0]
num = 0
for i in range(len(S)):
    num += int(S[i]) * (10**i)
    l.append(num % 2019)
# print(l)
ans = 0
c = Counter(l)
for v in c.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

# forを逆から回して下から素直にmodを取るとTLEだった
# 累積和的な計算で高速化、やりやすくするためにreverse
S = input()[::-1]
# ex. 1817181712114 → 4112171817181
# print(S)

# 0桁目までのMODを0とすることで、
# 1桁目を含む数が2019の倍数の時に都合が良くなる
X = [0]

# 4,14,114,2114,12114,...のmod2019を計算

for i, s in enumerate(S):
    X.append((X[-1] + int(s) * 10 ** i) % 2019)
# print(X)


C = Counter(X)
# print(C)

ans = 0
# Xが同じになったところを2つ選べば題意を満たす
# v_C_2の計算
for v in C.values():
    ans += v * (v - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
# S='201911'のとき、
# 201911 - 11 は2019の倍数
# T_k = (左から0始まりでk番目から末尾までの数)として
# T_(i) ≡ T_(j) mod 2019 ならばOK

seen_T_mod = {}

for i in range(len(S) + 1):
    T = S[i:]
    if T == '':
        T = '0'
    T_mod = int(T) % 2019
    if T_mod in seen_T_mod:
        seen_T_mod[T_mod] += 1
    else:
        seen_T_mod[T_mod] = 1

total = 0
for mod in seen_T_mod:
    if seen_T_mod[mod] > 1:
        total += seen_T_mod[mod] * (seen_T_mod[mod] - 1) // 2


print(total)

Submission status: Time Limit Exceeded

Solution code:
S = input()
# S='201911'のとき、
# 201911 - 11 は2019の倍数
# T_k = (左から0始まりでk番目から末尾までの数)として
# T_(i) ≡ T_(j) mod 2019 ならばOK

T_mod_list = [int(S[k:]) % 2019 for k in range(len(S))]
T_mod_list.append(0)
seen_T_mod = set()
total = 0
for T_mod in T_mod_list:
    if not T_mod in seen_T_mod:
        seen_T_mod.add(T_mod)

        count = T_mod_list.count(T_mod)
        
        if count > 1:
            total += count * (count - 1) // 2

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
cnt = 0
for i in range(len(S)-3):
    mul3 =0
    num = 0
    for j in range(i,len(S)):
        mul3 = (mul3 + int(S[j]))%3
        num = num*10+int(S[j])
        if mul3 == 0:
            if num%2019 ==0:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
def main():
    S = input()

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    S = input()

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S,r = input(),0
dp = list(range(len(S)+1))
dp[-1],dp[-2] = 0,int(S[-1])

for i in range(3,len(S)+2):
	dp[-i] = (dp[-i+1] + 10**(i-2)*int(S[-i+1])) % 2019

c = Counter(dp)
for x in c.values():
	r += x*(x-1)//2
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S,r = input(),0
dp = list(range(len(S)+1))
dp[-1],dp[-2] = 0,int(S[-1])

for i in range(3,len(S)+2):
	dp[-i] = (dp[-i+1] + 10**(i-2)*int(S[-i+1]))%2019

for x in Counter(dp).values():
	r += x*(x-1)//2
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
S = input()
l = len(S)
d = {l: 0}
for i in range(len(S)):
    s = int(S[i:l])
    d[i] = s%2019
count_d = defaultdict(int)
for i in range(len(S)+1):
    count_d[d[i]] += 1
counter = 0
for key in count_d.keys():
    counter += count_d[key] - 1
print(counter)

Submission status: Time Limit Exceeded

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