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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = (input())

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest


def resolve():
    s = list(input())
    lens = len(s)

    l = []
    tmp = 1

    while 1:
        l.append(str(tmp * 2019))
        tmp += 1
        if tmp * 2019 > 200000:
            break

    set_l = set(l)

    ans = 0

    for i in range(lens - 3):
        for j in range(i + 3, lens):
            if ''.join(s[i:j+1]) in set_l:
                ans += 1

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1817181712114"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """14282668646"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """2119"""
        output = """0"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=[0]*2019
while s:
    l[int(s)%2019]+=1
    s=s[1:]

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
c = 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:
            c += 1
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

def main():
    s = input()
    l = len(s)
    counter = 0
    for i in range(l-1):
        for j in range(i+1,l):
            number = int(s[i:j+1])
            if number % 2019 == 0:
                counter += 1

    print(counter)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
#何桁とるかで考える
count = 0
for i in range(len(s)):
    if i <= 3:
        continue
    else:
        for j in range(len(s)):
            if i+j <= len(s):
                if int(s[j:j+i])%2019 == 0:
                    count += 1
                
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

print(match)

Submission status: Time Limit Exceeded

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

def slove(t):
    cnt = 0
    for i in range(n-3):
        for j in range(i+3,n):
            p = int(s[i:(j+1)])
            if p%2019 == 0:
                cnt += 1
    print(cnt)


if n <= 3:
    print(0)
else:
    slove(n)

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(S: str):
    ct = 0
    for i in range(len(S)):
        for j in range(i, len(S)):
            s = S[i:(j+1)]
            si = int(s)
            if si % 2019 == 0:
                ct += 1
    print(ct)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

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)):
    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)):
        #print(i,j)
        num = int(s[i:j+1])

        if num % 2019 == 0:
            #print(i,j)
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input
S = input()

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

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

l_sum = [0]
for i in range(n):
    x = (l_sum[-1] + int(s[n-i-1]) * (10 ** i)) % 2019
    l_sum.append(x)

#print(l_sum)
l_sum.sort()
ans = 0
tmp = 0
cnt = 1
for i in range(1, len(l_sum)):
    if l_sum[i] == tmp:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = l_sum[i]

ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
for i,x in enumerate(s):
    now += int(x)*10**i
    now %= 2019
    data[now] += 1
    #print(now)

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    S = input()
    LIST = []
    for i in range(2000):
        LIST.append(2019*i)
    start = 0
    cnt = 0
    while start+4 < len(S):
        for i in range(start+4,len(S)+1):
            #print(S[start:i])
            if int(S[start:i]) in LIST:
                cnt += 1
        start += 1
    print(cnt)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
c = 0

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

print(c)

Submission status: Time Limit Exceeded

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:

A = input()
a = int(A)
ans  = 0 
for i in range(len(A)):
    for j in range(i+4,len(A)+1):
        t = A[i:j]
        ans += (int(t)%2019==0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
b = set([2019*x for x in range(1, 200000//2019 + 1)])

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

Submission status: Time Limit Exceeded

Solution code:
#D

#デバッグ
debug=1
def pront(*n):
    if debug==0:
        print(n)
        
#10**9+7を底とした処理

base=10**9+7

def add(a,b):#a+b
    return (a+b)%base

def sub(a,b):#a-b
    return (a-b)%base

def multi(a,b):#a*b
    return (a*b)%base

def exp(a,b):#a**b
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

def div(a,b):#a/b
    return(multi(a,exp(b,base-2)))

#入力

S=input()


#処理
L=len(S)
#明らかに時間超過しそう
x=0
for i in range(L+1):
    for j in range(i):
       # pront(i,j,S[j:i])
        if int(S[j:i])%2019==0:
            pront(j,i)
            x+=1
print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    S=int(input())
    SS=str(S)
    ls=len(SS)
    cnt=0
    for i in range(ls-3):
        for j in range(i+4,ls+1):
            if int(SS[i:j])%2019==0:
                cnt+=1
    print(cnt)


resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    l = len(s)
    ans = 0

    for i in range(0,l-3):
        n = int(s[i])*100 + int(s[i+1])*10 + int(s[i+2])
        for j in range(i+3,l):
            n = n*10 + int(s[j])
            if n % 2019 == 0:
                ans += 1
            
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# ABC164d


def main():
    import sys
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

    s = input()

    def prime_factorize(n):  # 素因数分解
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a

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

    # print(prime_factorize(2019))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
S = [int(x) for x in input()]
N = len(S)
l = 1
ans = 0
dic = defaultdict(int)
dic[0] = 1
m = 0
for x in S[::-1]:
    m = (x * l + m) % 2019
    ans += dic[m]
    l *= 10
    dic[m] += 1
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):
        if int(s[j:j + i + 1]) % 2019 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
cnt = 0
for i in range(l-1):
    for j in range(i+1, l):
        if eval(s[i:j+1]+'%2019') == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
A=[0]
for i in range(N):
    s=int(S[N-1-i:N])
    A.append(s%2019)
d={}
for i in range(len(A)):
    if not A[i] in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1
ans=0
for k in d.keys():
    ans+=d[k]*(d[k]-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=str(input())
m=0
for j in range(len(S)-3):
  i=j+3
  while True:
    if int(S[j:i])%2019==0:
      m+=1
print(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
s = str(input())
n = len(s)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

l = len(S)

cnt = 0
for i in range(l):
    for j in range(i+3, l):
        if int(S[i : j + 1]) % 2019 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = read().decode().rstrip()

l = 0
r = 0

cnt = 0
while l < len(S):
    r = l
    while r < len(S):
        acc = S[l:r + 1]
        if int(acc) % 2019 == 0:
            cnt += 1
        r += 1
    l += 1

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    l = set([str(i*2019) for i in range(1, 101)])
    S = input()
    ans = 0
    for i in range(len(S)):
        for j in range(i+1, len(S)):
            if S[i:j+1] in l:
                ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

print(ctr)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


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

    U = [0]*(N+1)
    a = 0
    # for i in range(N-1, -1, -1):
    for i in range(N):
        a += (10**i)*int(S[N-1-i])
        a %= 2019
        U[i] = a
    # U = [int(S[i:]) % 2019 for i in range(N)] + [0]
    table = [0]*2019

    tot = 0
    # for i in range(N-1, -1, -1):
    for i in range(N):
        tot += table[U[N-1-i]]
        table[U[N-1-i]] += 1
    tot += table[0]
    print(tot)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
N = len(list(S))
for i in range(N+1):
    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:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    s = int(input())

    power = 10
    dic = [0] * 2019
    dic[0] = 1
    for _ in range(len(str(s))):
        x = s%power%2019
        dic[x] += 1
        power *= 10
    
    ans = 0
    for v in dic:
        ans += v*(v - 1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    if len(s)<4:
        print(0)
        exit()
    
    i=0
    j=4
    ans=0
    while i<=len(s)-4:
        tmp=int(s[i:j])
        if tmp%2019==0:ans+=1
        j+=1
        if j==len(s)+1:
            i+=1
            j=i+4
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

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

Submission status: Time Limit Exceeded

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

R = [0]*2019

for i in range(n):
    s = int(S[-i-1:])
    R[s % 2019] += 1

ans = R[0]
for r in R:
    ans += r*(r-1)//2

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    s = int(input())

    power = 10
    dic = {i:0 for i in range(2019)}
    dic[0] = 1
    for _ in range(len(str(s))):
        x = s%power%2019
        dic[x] += 1
        power *= 10
    
    ans = 0
    for v in dic.values():
        ans += v*(v - 1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
s=ss()
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:
s=input()
ans=0
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if int(s[i:j])%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(S: str):
    N = len(S)
    U = [int(S[i:]) % 2019 for i in range(N)] + [0]
    table = [0]*2019

    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    answer = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            now = int(s[i:j + 1])
            if now < 2019:
                continue
            elif now % 2019 == 0:
                answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read


s = input()

MOD = 2019
d = [0]*MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    d[r] += 1
    
print(sum(i*(i-1)//2 for i in d))

Submission status: Accepted

Solution code:
S = input()
mod = 2019

array = []
for i in range(len(S)):
    x = (int(S[len(S)-1-i])*pow(10,i,mod))%mod
    array.append(x)
array2 = [0]
y = 0
for i in range(len(S)):
    y = (y+array[i])%mod
    array2.append(y)
array3 = [0] * 2019
ans = 0
for i in range(len(array2)):
    z = array2[i]
    ans += array3[z]
    array3[z] += 1
print(ans)
#3*673

Submission status: Accepted

Solution code:
s = input()
t = s[::-1]
n = len(s)
resid = [0] * 2019
resid[0] = 1
csum = 0
powoften = 1
for i in range(n):
    csum = (csum + int(t[i]) * powoften) % 2019
    powoften = (10 * powoften) % 2019
    resid[csum] += 1
ans = 0
for i in range(2019):
    ans += resid[i] * (resid[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def inp():
    return int(input())
def inps():
    return input().rstrip()
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

# ---------------------------------------

mod = 2019
S = inps()
dp = [0] * len(S)
mp = {}
ten = 1
for i in range(len(S)-1, -1, -1):
    n = int(S[i])
    if i == len(S) - 1:
        dp[i] = n % mod
    else:
        ten = (ten * 10) % mod
        dp[i] = (dp[i + 1] + n * ten) % mod
    if dp[i] in mp:
        mp[dp[i]] += 1
    else:
        mp[dp[i]] = 1

ans = 0
for k, v in mp.items():
    if k == 0:
        ans += v
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s=list(map(int,input()))
c=0
cnt=[0]*2019
cnt[0]+=1
for k in range(len(s)-1,-1,-1):
	c=(c+s[k]*pow(10,len(s)-1-k,2019))%2019
	cnt[c]+=1
print(sum(x*(x-1)//2 for x in cnt))

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarizeList(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

# 累積和の書き方がよくないやつ
def main():
  s=S()
  n=len(s)

  l=[]
  mul=1
  for x in s[::-1]:
    l.append(mul*int(x)%2019)
    mul*=10
    mul%=2019

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

  sl=summarizeList(l)
  # print(sl)

  ans=0
  for x,c in sl:
    if x==0:
      ans+=c
    if c>1:
      ans+=c*(c-1)//2

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)

Submission status: Accepted

Solution code:
n = input()
p = 2019
t = 1
y = 0
c = p*[0]

for x in map(int,n[::-1]):
  y+=t*x
  y%=p
  c[y]+=1
  t*=10
  t%=p

print(sum(i*(i-1)//2 for i in c)+c[0])

Submission status: Accepted

Solution code:
s=list(input())
l=[0]*2019
t=0
ans=0
for i in range(len(s)):
    t=(t+pow(10,i,2019)*int(s[-1-i]))%2019
    l[t]+=1
for i in l:
    ans+=(i*(i-1))//2
print(ans+l[0])

Submission status: Accepted

Solution code:
def egcd(a, b):
    """Returns a triple (g, x, y), such that ax + by = g = gcd(a,b).
       Assumes a, b >= 0, and that at least one of them is > 0.
       Bounds on output values: |x|, |y| <= max(a, b)."""
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m) 
    if g != 1:
        return None
    else:
        return x % m

def main():
    s = input()
    n = len(s)
    h = [0]
    for i in range(n):
        h.append((h[-1] * 10 + int(s[i])) % 2019)
    p = [1]
    for i in range(n):
        p.append((p[-1] * 10) % 2019)
    lk = {0 : 1}
    cnt = 0
    for i in range(1, len(h)):
        curr = (h[i] * modinv(p[i], 2019)) % 2019
        # print(i, curr)
        if curr in lk:
            cnt += lk[curr]
            lk[curr] += 1
        else:
            lk[curr] = 1 
    print(cnt)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S=input()
s=int(S)
mod=2019
c=[0]*(len(S)+1)
d=[0]*2019


c[0]=0
d[0]=1
for i in range(len(S)):
  c[i+1]=(c[i]+int(S[-i-1])*pow(10,i,mod))%mod
  d[c[i+1]]+=1
  
m=0
for i in range(2019):
  m+=d[i]*(d[i]-1)//2

print(m)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()
kTarget = 2019

mod2cnt = defaultdict(int)
mod2cnt[0] += 1

ord_z = ord('0')
res = 0
for i in range(len(S)-1, -1, -1):
    d = ord(S[i]) - ord_z
    res = (res+d*pow(10, len(S)-1-i, kTarget))%kTarget
    mod2cnt[res] += 1

ans = 0
for cnt in mod2cnt.values():
    ans += cnt*(cnt-1)
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    S = input()

    mods = [0] * 2019

    ttl = 0
    pows = 1

    for i in range(len(S)-1, -1, -1):
        ttl += (int(S[i]) * pows) % 2019
        ttl %= 2019
        pows *= 10
        pows %= 2019
        mods[ttl] += 1

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

    print(int(ans))


main()

Submission status: Accepted

Solution code:
ans=0
S=input()
a=len(S)
k=0
c=dict()
mod=2019
s=1
c[0]=1
for i in range(a):
  k+=(s*int(S[a-i-1]))
  k%=mod
  s*=10
  s%=mod
  if k in c:
    c[k]+=1
  else:
    c[k]=1
for i in c:
  ans+=c[i]*(c[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()
mod = 2019

t = len(S)
l = [0] * (t + 1)
for i in range(t-1, -1, -1):
    l[i] = (l[i+1] + int(S[i]) * pow(10, t-i-1, mod)) % mod

from collections import Counter

def nC2(n):
    return n * (n - 1) // 2

l = list(Counter(l).values())

ans = 0
for i in l:
    ans += nC2(i)

print(ans)

Submission status: Accepted

Solution code:
s=input()

s=s[::-1]

counts = [0] * 2019
counts[0] = 1

num=0
d = 1


for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1
    
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力