Problem:


Score : 1800 points

Problem Statement

For a sequence S of positive integers and positive integers k and l, S is said to belong to level (k,l) when one of the following conditions is satisfied:

The length of S is 1, and its only element is k.

There exist sequences T_1,T_2,...,T_m (m \geq l) belonging to level (k-1,l) such that the concatenation of T_1,T_2,...,T_m in this order coincides with S.

Note that the second condition has no effect when k=1, that is, a sequence belongs to level (1,l) only if the first condition is satisfied.

Given are a sequence of positive integers A_1,A_2,...,A_N and a positive integer L.
Find the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i  \leq j \leq N) that satisfy the following condition:

There exists a positive integer K such that the sequence A_i,A_{i+1},...,A_j belongs to level (K,L).

Constraints

1 \leq N \leq 2 \times 10^5

2 \leq L \leq N

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N L
A_1 A_2 ... A_N

Output

Print the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i  \leq j \leq N) that satisfy the condition.

Sample Input 1

9 3
2 1 1 1 1 1 1 2 3

Sample Output 1

22

For example, both of the sequences (1,1,1) and (2) belong to level (2,3), so the sequence (2,1,1,1,1,1,1) belong to level (3,3).

Sample Input 2

9 2
2 1 1 1 1 1 1 2 3

Sample Output 2

41

Sample Input 3

15 3
4 3 2 1 1 1 2 3 2 2 1 1 1 2 2

Sample Output 3

31



Sample input:
9 3
2 1 1 1 1 1 1 2 3


Sample output:
22

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
import sys

def resolve():
	input = sys.stdin.readline

	N, L = list(map(int,input().strip().split()))
	alist = list(map(int,input().strip().split()))

	# print(alist)

	count = N 	# 1 factor array must satisfy the condition
	for x in itertools.combinations(range(N), 2):
		i, j = x[0], x[1]

	# for x in range(1):
		# i, j = 0,8

		target_list = alist[i:j+1]
		maximum = max(target_list)
		level_count = np.zeros(maximum, 'int64')
		pre_num = maximum
		condition = True

		for index in range(len(target_list)):
			target = target_list[index]
			level_count[target-1] = level_count[target-1]+1

			if target>pre_num:
				for ti in range(target-1):
					if level_count[ti]!=0:
						moveup = int(level_count[ti]/L)
						if moveup==0:
							condition = False
							break
						else:
							level_count[ti+1] = level_count[ti+1]+moveup
							level_count[ti] = 0

			if condition==False:
				break
			else:
				pre_num = target

		if condition==True:
			for ti in range(maximum-1):
				if level_count[ti]!=0:
					moveup = int(level_count[ti]/L)
					if moveup==0:
						condition = False
						break
					else:
						level_count[ti+1] = level_count[ti+1]+moveup
						level_count[ti] = 0

			if (condition==True) and (level_count[-1]>=L):
				count = count+1
				# print(i,j)

	print(count)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
import sys

def main():
	input = sys.stdin.readline

	N, L = list(map(int,input().strip().split()))
	alist = list(map(int,input().strip().split()))

	count = N 	# 1 factor array must satisfy the condition
	for x in itertools.combinations(range(N), 2):
		i, j = x[0], x[1]

	# for x in range(1):
		# i, j = 0,8

		target_list = alist[i:j+1]
		maximum = max(target_list)
		level_count = np.zeros(maximum, 'int64')
		pre_num = maximum
		condition = True

		for index in range(len(target_list)):
			target = target_list[index]
			level_count[target-1] = level_count[target-1]+1

			if target>pre_num:
				for ti in range(target-1):
					if level_count[ti]!=0:
						moveup = int(level_count[ti]/L)
						if moveup==0:
							condition = False
							break
						else:
							level_count[ti+1] = level_count[ti+1]+moveup
							level_count[ti] = 0

			if condition==False:
				break
			else:
				pre_num = target

		if condition==True:
			for ti in range(maximum-1):
				if level_count[ti]!=0:
					moveup = int(level_count[ti]/L)
					if moveup==0:
						condition = False
						break
					else:
						level_count[ti+1] = level_count[ti+1]+moveup
						level_count[ti] = 0

			if (condition==True) and (level_count[-1]>=L):
				count = count+1
				# print(i,j)

	print(count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
import sys

def main():

	input = sys.stdin.readline

	N, L = list(map(int,input().strip().split()))
	alist = list(map(int,input().strip().split()))

	count = N 	# 1 factor array must satisfy the condition
	for x in itertools.combinations(range(N), 2):
		i, j = x[0], x[1]

	# for x in range(1):
		# i, j = 0,8

		target_list = alist[i:j+1]
		maximum = max(target_list)
		level_count = np.zeros(maximum, 'int64')
		pre_num = maximum
		condition = True

		for index in range(len(target_list)):
			target = target_list[index]
			level_count[target-1] = level_count[target-1]+1

			if target>pre_num:
				for i in range(target-1):
					if level_count[i]!=0:
						moveup = int(level_count[i]/L)
						if moveup==0:
							condition = False
							break
						else:
							level_count[i+1] = level_count[i+1]+moveup
							level_count[i] = 0

			if condition==False:
				break
			else:
				pre_num = target

		if condition==True:
			for i in range(maximum-1):
				if level_count[i]!=0:
					moveup = int(level_count[i]/L)
					if moveup==0:
						condition = False
						break
					else:
						level_count[i+1] = level_count[i+1]+moveup
						level_count[i] = 0

			if (condition==True) and (level_count[-1]>=L):
				count = count+1
				# print(i,j)

	print(count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools


N, L = list(map(int,input().strip().split()))
alist = list(map(int,input().strip().split()))

count = N 	# 1 factor array must satisfy the condition
for x in itertools.combinations(range(N), 2):
	i, j = x[0], x[1]

# for x in range(1):
# 	i, j = 0,3

	target_list = alist[i:j+1]
	maximum = max(target_list)
	k = maximum+1 # level
	needed_length = L**(k-2)
	length = 0
	condition = True
	count1 = 0
	belowlevel = 0

	for index in range(len(target_list)):
		if target_list[index]==1:
			count1 = count1+1

			if index==len(target_list)-1:
				cluster_num = int(count1/L)
				if cluster_num==0:
					condition = False
					break
				else:
					length = length+cluster_num
					count1 = 0
			elif target_list[index+1]!=1:
				cluster_num = int(count1/L)
				if cluster_num==0:
					condition = False
					break
				else:
					length = length+cluster_num
					count1 = 0
		elif target_list[index]==maximum:
			belowlevel= belowlevel+1+int(length/(needed_length/L))
			length = 0
		else:
			length = length+L**(target_list[index]-2)

	belowlevel = belowlevel+int(length/(needed_length/L))

	if (length!=0) and (length<needed_length/L):
		condition = False

	if (condition==True) and belowlevel>=L:
		count = count+1
		# print(i,j)

print(count)

Submission status: Runtime Error

Solution code:
import itertools


N, L = list(map(int,input().strip().split()))
alist = list(map(int,input().strip().split()))

count = N 	# 1 factor array must satisfy the condition
for x in itertools.combinations(range(N), 2):
	i, j = x[0], x[1]
	# print(i,j)

# for x in range(1):
# 	i, j = 1,8

	target_list = alist[i:j+1]
	maximum = max(target_list)
	k = maximum+1 # level
	needed_length = L**(k-2)
	length = 0
	condition = True
	count1 = 0
	belowlevel = 0

	for index in range(len(target_list)):
		if target_list[index]==1:
			count1 = count1+1

			if index==len(target_list)-1:
				cluster_num = int(count1/L)
				if cluster_num==0:
					condition = False
					break
				else:
					length = length+cluster_num
					count1 = 0
			elif target_list[index+1]!=1:
				cluster_num = int(count1/L)
				if cluster_num==0:
					condition = False
					break
				else:
					length = length+cluster_num
					count1 = 0
		elif target_list[index]==maximum:
			belowlevel= belowlevel+1+int(length/(needed_length/L))
			length = 0
		else:
			length = length+L**(target_list[index]-2)

	belowlevel = belowlevel+int(length/(needed_length/L))

	if (length!=0) and (length<needed_length/L):
		condition = False

	if (condition==True) and belowlevel>=3:
		count = count+1
		# print(i,j)

print(count)