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)
a = [0]*(n+1)
l = [0]*2019
t = pow(10, n-1)

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i])*t
    l[a[i+1]%2019] += 1
    t = t // 10

print(sum(map(lambda x: x*(x-1)//2, l)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
a = [0]*(n+1)
l = [0]*2019

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i]+'0'*(n-i-1))
    l[a[i+1]%2019] += 1

print(sum(map(lambda x: x*(x-1)//2, l)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
a = [0]*(n+1)
l = [0]*2019

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i])*pow(10, n-i-1)
    l[a[i+1]%2019] += 1

print(sum(map(lambda x: x*(x-1)//2, l)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
a = [0 for _ in range(n+1)]
l = [0 for _ in range(2019)]

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i])*pow(10, n-i-1)
    l[a[i+1]%2019] += 1

print(sum(map(lambda x: x*(x-1)//2, l)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S = input()
n = len(S)
a = [int(S)]
cnt = 0

for i in range(n):
    a.append(a[i] - int(S[i])*(10**(n-i-1)))

a = Counter(list(map(lambda x: x%2019, a)))


for k, v in a.items():
    cnt += v*(v-1)//2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
a = [int(S)]
cnt = 0

for i in range(n):
    a.append(a[i] - int(S[i])*(10**(n-i-1)))

a = list(map(lambda x: x%2019, a))

for i in range(2019):
    tmp = a.count(i)
    cnt += tmp*(tmp-1)//2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
import collections


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    input = stdin.readline
    s = list(input()[:-1])
    s = list(map(int, s))
    N = len(s)
    mod = [0] * N
    mod[-1] = s[-1] % 2019
    for i in reversed(range(N - 1)):
        mod[i] = (mod[i + 1] + s[i] * 10 ** (N - i - 1)) % 2019

    fac, finv = initialize_cmb(N)

    counter = collections.Counter(mod)

    ans = 0

    for k, v in counter.items():
        if k == 0:
            ans += v
        elif v > 1:
            ans += cmb(v, 2, fac, finv)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
import collections


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    input = stdin.buffer.readline
    s = input()[:-1].decode()
    N = len(s)
    mod = [0] * N
    for i in range(N):
        mod[i] = int(s[i:N]) % 2019

    fac, finv = initialize_cmb(N)

    counter = collections.Counter(mod)

    ans = 0

    for k, v in counter.items():
        if k == 0:
            ans += v
        elif v > 1:
            ans += cmb(v, 2, fac, finv)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    input = stdin.buffer.readline
    s = input()[:-1].decode()
    N = len(s)
    mod = [0] * N
    for i in range(N):
        mod[i] = int(s[i:N]) % 2019

    fac, finv = initialize_cmb(N)

    ans = mod.count(0)

    for i in range(2019):
        ans += cmb(mod.count(i), 2, fac, finv)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
lst = []
for i in range(len(s)):
    lst.append(int(s[-1-i:]) % 2019)
lst.sort()

total = 0
cnt = 1
before = 0
for num in lst:
    if before == num:
        cnt += 1
    else:
        total += cnt * (cnt - 1) // 2
        cnt = 1
    before = num
total += cnt * (cnt - 1) // 2
print(total)

Submission status: Time Limit Exceeded

Solution code:
N=list(input())

count=0

for i in range(len(N)-3):
    for j in range(i+4,len(N)+1):
        B=int(''.join(N[i:j]))
        if B%2019==0:
            count+=1
        else:
            pass
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = input().rstrip()
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    for i, c in enumerate(S[::-1]):
        num += int(c) * (10**(i)%mod)
        num %= mod
        counter[num] += 1
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = reversed(list(input().rstrip()))
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    for i, c in enumerate(S):
        num += int(c) * 10**(i)
        counter[num%mod] += 1
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = int(input())
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    for i in range(200001):
        x = S % (10**(i+1))
        counter[x%mod] += 1
        if x == S:
            break
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = (int(X)*(10**(i))) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*(10**(i))+S
  mod_val=(S % 2019)
  mod_count.append(mod_val)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = input()
count=0
S=[0]
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S.append(int(X)*(10**(int(i+1)-1))+S[i])
  mod_val=(S[i+1] % 2019)
  mod_count.append(mod_val)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = input()
count=0
S=[0]
mod_count=[]
ans=0
for K in range(1,len(N)+1):
  S.append(int(N[-K])*(10**(K-1))+S[K-1])
for X in S:
  mod_val=(X % 2019)
  mod_count.append(mod_val)

c = Counter(mod_count)

for Y in c.values():
  ans+= Y*(Y-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = input()
count=0
S=[0]
mod_count=[]
ans=0
for K in range(1,len(N)+1):
  S.append(int(N[-K])*(10**(K-1))+S[K-1])
for X in S:
  mod_val=(X % 2019)
  mod_count.append(str(mod_val))

c = Counter(mod_count)

for Y in c.values():
  ans+= Y*(Y-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = input()
count=0
S=[0]
mod_count=[]
ans=0
for K in range(1,len(N)+1):
  S.append(int(N[-K:]))
for X in S:
  mod_val=(X % 2019)
  mod_count.append(str(mod_val))

c = Counter(mod_count)

for Y in c.values():
  ans+= Y*(Y-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = int(i) * d + last
    last = num
    num %= 2019
    d *= 10
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
num = 0
last = 0
d = 1
count = [0] * 2019 # 余りの格納箱
count[0] =1  # 割り切れるとき
for i in s:
    num = int(i) * d + last
    last = num
    num %= 2019
    d *= 10
    count[num] += 1
    
ans = 0
for i in count:
    ans += i * (i-1) //2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = [0]
for i in range(n - 1, -1, -1):
    mod_list.append((mod_list[-1] + int(s[i]) * 10**(n - 1 - i) ) % mod)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = []
for i in range(n):
    s_ = s[i:]
    mod_list.append(int(s_) % mod)
mod_list.append(0)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

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

def check(ij):
    ss = int(s[ij[0]-1:ij[1]])
    if ss % 2019 == 0:
        return True
    else:
        return False
    

def dfs(ij):
    global count
    if len(ij) == 2:
        if check(ij):
            count += 1
    elif len(ij) == 1:
        for k in range(ij[0]+3, n+1):
            ij.append(k)
            dfs(ij)
            ij.pop()
    else:
        for k in range(1, n-2):
            ij.append(k)
            dfs(ij)
            ij.pop()
            
dfs([])
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

def shift(s):
    global dp
    dp = np.roll(dp, s)

ans = 0
for i, s in enumerate(S[::-1]):
    shift(int(s) * pow(10, i, MOD) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

ans = 0
for i, s in enumerate(S[::-1]):
    dp = np.roll(dp, int(s) * pow(10, i, MOD) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
count=0
for i in range(len(N)+1):
  for j in range(i+1,len(N)+1):
    if(int(N[i:j])%3!=0):
      continue
    if(int(N[i:j])%673==0):
      count+=1

print(count)

Submission status: Time Limit Exceeded

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

def hoge(dp, s):
    T = dp.copy()
    dp[s:] = T[:-s]
    dp[:s] = T[-s:]

def huga(dp, s):
    T = dp.copy()
    for i in range(MOD):
        dp[i] = T[(i - s) % MOD]

ans = 0
for i, s in enumerate(S[::-1]):
    huga(dp, (int(s) * pow(10, i, MOD)) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
mod=2019
S=list(reversed(S))
N=len(S)
A=[0]*(N)
p=1
for i in range(N):
    p=(10**i)%mod
    now=(int(S[i])*p)%mod
    A[i]=now
    #print(now)
rui=[0]*(N+1)
for i in range(1,N+1):
    rui[i]=(rui[i-1]+A[i-1])%mod
total=[0]*2019
for r in rui:
    total[r]+=1
ans=0
for t in total:
    ans+=t*(t-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

dp = [0] * (len(S) + 1)
for i, c in enumerate(S):
    dp[i + 1] = 10 * dp[i] + int(c) % 2019
for i, _ in enumerate(dp):
    dp[i] *= pow(10, -i, 2019)
    dp[i] %= 2019

counts = [0] * 2019
for c in dp:
    counts[c] += 1

result = 0
for count in counts:
    result += count * (count - 1) // 2

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 2019

from collections import defaultdict

S = list(input())
dic = defaultdict(int)
dic[0] += 1

ans = 0
x = 0
count = 0
for s in S[::-1]:
    x += int(s) * pow(10, count)
    x %= MOD
    ans += dic[x]
    dic[x] += 1
    count += 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 2019

from collections import defaultdict

S = list(input())
dic = defaultdict(int)
dic[0] += 1

ans = 0
x = 0
count = 0
for s in S[::-1]:
    x += int(s) * pow(10, count)
    ans += dic[x % MOD]
    dic[x % MOD] += 1
    count += 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
m = set(str(i*2019) for i in range(200))
count = 0
for i in range(len(s)-1):
    for j in range(i+2,len(s)+1):
        if "".join(s[i:j]) in m:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

main()

Submission status: Time Limit Exceeded

Solution code:
N = input("")
l = len(N)
c = 0

if l>=4:
    for i in range(l-3):
        for k in range(l-3-i):
            n = N[k:k+4+i]
            if int(n)%2019 == 0:
                c += 1
else:
    c = 0

print(c)

Submission status: Time Limit Exceeded

Solution code:
N = input("")
Nn = " ".join(N)
NN = Nn.split(" ")
l = len(NN)
c = 0

if l>=4:
    for i in range(l-3):
        for k in range(l-3-i):
            n = N[k:k+4+i]
            if int(n)%2019 == 0:
                c += 1
else:
    c = 0

print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
#簡単にするためにひっくり返す
N = len(S)

A=[0]*2019
number=0
A[0]=1
#０を２０１９で割った余りは０
d=1

ans=0

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d *= 10

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

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

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()[::-1]
N = len(S)
l = [0]*N
for i in range(N):
    l[i] = (l[i-1]+int(S[i])*(10**i))%2019
c = Counter(l)
c[0] += 1
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10

print(result)

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  d *= 10

print(sum([i*(i-1)//2 for i in counter]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = defaultdict(int)
counter[mods[-1]] += 1
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  d *= 10

print(sum([i*(i-1)//2 for i in counter.values()]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = defaultdict(int)
counter[mods[-1]] += 1
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  d *= 10
  
result = 0
for j in counter.values():
  if j >= 2:
    result += j*(j-1)//2
print(result)

Submission status: Time Limit Exceeded

Solution code:
import collections
S = input()
S = S[::-1]
d = 1
mods = [0]
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  d *= 10
  
c = collections.Counter(mods)
result = 0
for i,j in c.most_common():
  if j >= 2:
    result += j*(j-1)//2
print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
si=int(s)
mod=2019
t={}
t[si%mod]=1
for i in range(n):
    si-=int(s[i])*pow(10,n-1-i,mod)
    a=si%mod
    if a in t:
        t[a]+=1
    else:
        t[a]=1
ans=0
for v in t.values():
    ans+=(v*(v-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
for i in range(n):
    t = int(string[i])*(10**i)+S[i]
    t = t % 2019
    S.append(t)

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

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

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
si=int(s)
mod=2019
from collections import defaultdict
t=defaultdict(lambda:0)
for i in range(n):
    t[int(s[i:])%mod]+=1
t[0]+=1
ans=0
for v in t.values():
    ans+=(v*(v-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
si=int(s)
mod=2019
t=[si%mod]
for i in range(n):
    si-=int(s[i])*pow(10,n-1-i)
    t.append(si%mod)
from collections import Counter
d=Counter(t)
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
t=[]
mod=2019
for i in range(n):
    t.append(int(s[i:])%mod)
t.append(0)
from collections import Counter
d=Counter(t)
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
t=[]
mod=2019
for i in range(n):
    a=0
    for j in range(i,n):
        a+=pow(10,n-1-j)*int(s[j])
    t.append(a%mod)
t.append(0)
from collections import Counter
d=Counter(t)
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
res = 0
for i in range(n):
    sum = int(s[i])
    for j in range(i + 1, n):
        num = int(s[j])
        sum = sum * 10 + num
        if sum % 2019 == 0:
            res += 1

print(res)

Submission status: Time Limit Exceeded

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

l = [0 for i in range(2019)]
n = len(s)
l[0] = 1
prev = 0
digit = 1
for c in s:
    t = (int(c) * digit + prev) % 2019
    l[t] += 1
    digit = digit * 10
    prev = t

res = 0
for i in l:
    res += i * (i-1) // 2

print(res)

Submission status: Time Limit Exceeded

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

l = [0 for i in range(2019)]
n = len(s)
l[0] = 1
prev = 0
for i in range(n-1,-1,-1):
    a = s[i]
    t = prev + a*10**(n-i-1)
    tmod = t % 2019
    l[tmod] += 1
    prev = tmod

res = 0
for i in l:
    res += i * (i-1) // 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()

l = [0 for i in range(2019)]
n = len(s)
s_int = int(s)

for i in range(n+1):
    tmp = s_int % (10**i) % 2019 
    l[tmp] += 1

res = 0
for i in l:
    res += i * (i-1) // 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()

l = [0 for i in range(2019)]
n = len(s)
l[0] = 1

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

res = 0
for i in l:
    res += i * (i-1) // 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()

l = []
n = len(s)

for i in range(n):
    tmp = int(s[i:]) % 2019
    l.append(tmp)
l.append(0)
res = 0
for i in range(2018):
    count = l.count(i)
    res += count * (count-1) // 2

print(res)

Submission status: Time Limit Exceeded

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
s_re = S[::-1]

tot = 0
count = [0] * 2019
ans = 0

for i in range(N):
    count[tot] += 1
    tot += int(s_re[i])*(10**i)
    tot %= 2019
    ans += count[tot]

print(int(ans))

Submission status: Time Limit Exceeded

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

tot = 0
count = [0] * 2019
ans = 0

for i in range(N):
    count[tot] += 1
    tot += int(S[N-(i+1)])*(10**i)
    tot %= 2019
    ans += count[tot]

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
N = len(S)

tot = 0
count = np.zeros(2019)
ans = 0

for i in range(N):
    count[tot] += 1
    tot += int(S[N-(i+1)])*(10**i)
    tot %= 2019
    ans += count[tot]

print(int(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * 10**c for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([int(v * (v-1) / 2) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * 10**c for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([sum(range(v)) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1

for i in range(l):
	dp+=int(s[l-1-i])*r
	dp%=2019
	r*=10%2019
	d[dp]+=1

res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

Submission status: Time Limit Exceeded

Solution code:
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1

for i in range(l-1,-1,-1):
	dp+=int(s[i])*r
	dp%=2019
	r*=10%2019
	d[dp]+=1

res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

Submission status: Time Limit Exceeded

Solution code:
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1
for i in range(l-1,-1,-1):
	dp = (dp+int(s[i])*r)%2019
	r*=10%2019
	d[dp]+=1
res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

Submission status: Time Limit Exceeded

Solution code:
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)

for i in range(l-1,-1,-1):
	dp = (dp+int(s[i])*(10**(l-1-i)))%2019
	d[dp]+=1
res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s=input()
d=defaultdict(int)

dp=0
d[0]+=1
for i in range(len(s)-1,-1,-1):
	dp = (dp+int(s[i])*(10**(len(s)-1-i)))%2019
	d[dp]+=1
res=0

l=list(d.values())
for a in l:
	res+=a*(a-1)//2
	
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys

INF = 1145141919


def solve(S: int):
    ans = 0
    s = [0]+list(map(int, str(S)))
    for i in range(1, len(s)):
        s[i] = s[i-1]*10+s[i]
    for i in range(len(s)-4):
        for j in range(i + 4, len(s)):
            if (s[j] - s[i]*10**(j-i)) % 2019 == 0:
                ans += 1

    return ans


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = int(input())
n = len(str(s))
d = 1
cnt = [0]*2019
for i in range(n+1):
    cnt[(s%d)%2019] += 1
    d *= 10


#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


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

print(ans)

Submission status: Time Limit Exceeded

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

'''
slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)
cnt = [0]*2019

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()

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

Submission status: Time Limit Exceeded

Solution code:
s = int(input())
n = len(str(s))
slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)
cnt = [0]*2019

for m in slist:
    cnt[m] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
ans = S.count('0')
num = 0
for i in range(len(S)):
  for j in range(i+3,len(S)):
    num = ''.join(map(str,S[i:j+1]))
    if int(num) % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
ans = 0
num = 0
x = len(S)
sub = []
for i in range(x):
  for j in range(i,x):
    if i == j and S[i] == '0':
      ans += 1
    elif j-i >=  3:
      sub = S[i:j+1]
      num = ''.join(map(str,sub))
      if int(num) % 2019 == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
ans = 0
sub = []
num = 0
for i in range(len(S)):
  for j in range(i,len(S)):
    if i == j and S[i] == '0':
      ans += 1
    elif j-i >=  3:
      sub = S[i:j+1]
      num = ''.join(map(str,sub))
      if int(num) % 2019 == 0:
        ans += 1
print(ans)