Problem:


Score : 400 points

Problem Statement

There are N towns located in a line, conveniently numbered 1 through N. Takahashi the merchant is going on a travel from town 1 to town N, buying and selling apples.

Takahashi will begin the travel at town 1, with no apple in his possession. The actions that can be performed during the travel are as follows:

Move: When at town i (i < N), move to town i + 1.

Merchandise: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for A_i yen (the currency of Japan) at town i (1 ≦ i ≦ N), where A_i are distinct integers. Also, you can assume that he has an infinite supply of money.

For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most T. (Note that a single apple can be counted in both.)

During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.

Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change A_i into another arbitrary non-negative integer A_i' for any town i, any number of times. The cost of performing this operation is |A_i - A_i'|. After performing this operation, different towns may have equal values of A_i.

Aoki's objective is to decrease Takahashi's expected profit by at least 1 yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least 1 yen.

Constraints

1 ≦ N ≦ 10^5

1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)

A_i are distinct.

2 ≦ T ≦ 10^9

In the initial state, Takahashi's expected profit is at least 1 yen.

Input

The input is given from Standard Input in the following format:

N T
A_1 A_2 ... A_N

Output

Print the minimum total cost to decrease Takahashi's expected profit by at least 1 yen.

Sample Input 1

3 2
100 50 200

Sample Output 1

1

In the initial state, Takahashi can achieve the maximum profit of 150 yen as follows:

Move from town 1 to town 2.

Buy one apple for 50 yen at town 2.

Move from town 2 to town 3.

Sell one apple for 200 yen at town 3.

If, for example, Aoki changes the price of an apple at town 2 from 50 yen to 51 yen, Takahashi will not be able to achieve the profit of 150 yen. The cost of performing this operation is 1, thus the answer is 1.

There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town 3 from 200 yen to 199 yen.

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

2

Sample Input 3

10 100
7 10 4 5 9 3 6 8 2 1

Sample Output 3

2



Sample input:
3 2
100 50 200


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
l = list(map(int, input().split()))
n = l[0]
t = l[1]

l = list(map(int, input().split()))
maxdiff = 0
count = 0
startindex = 0
endindex = 0

currentIndex = 0
for currentIndex in range(n):
    maxnum = 0
    if l[currentIndex] > l[startindex] and currentIndex <= endindex:
        continue
    for j in range(currentIndex+1, n):
        if l[j] > maxnum:
            maxnum = l[j]
        else:
            continue
        if l[j] - l[currentIndex] > maxdiff:
            maxdiff = l[j] - l[currentIndex]
            count = 1
            startindex = currentIndex
            endindex = j
        elif l[j] - l[currentIndex] == maxdiff:
            count += 1
            startindex = currentIndex
            endindex = j
print(count)

Submission status: Time Limit Exceeded

Solution code:
l = list(map(int, input().split()))
n = l[0]
t = l[1]

l = list(map(int, input().split()))
maxdiff = 0
count = 0
minprice = None
maxprice = None

for i in range(n):
    for j in range(i+1, n):
        if l[j] - l[i] > maxdiff:
            maxdiff = l[j] - l[i]
            count = 1
        elif l[j] - l[i] == maxdiff:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

n,t = map(int, raw_input().split())
a = map(int, raw_input().split()) 

l,r = 0,0
diff = 0
num = 0
lp = 0
for l in range(n):
    if(a[lp]<a[l]):
        pass
    else:
        for r in range(l+1,n):
            #print(l,r)
            if(a[r]-a[l]>diff):
                lp = l
                diff = a[r]-a[l]
                num = 1
            elif(a[r]-a[l]==diff):
                num += 1
print(num)

Submission status: Time Limit Exceeded

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

n,t = map(int, raw_input().split())
a = map(int, raw_input().split()) 

l,r = 0,0
diff = 0
num = 0
lp = 0
for l in range(n):
    if(a[lp]<a[l]):
        pass
    else:
        lp = l
        for r in range(l+1,n):
            if(a[r]-a[l]>diff):
                diff = a[r]-a[l]
                num = 1
            elif(a[r]-a[l]==diff):
                num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int,input().split())
A = list(map(int,input().split()))
b = 0
Nc = 0
for i in range(len(A)-1):
    M = max(A[i+1:len(A)])
    b = max(b,M-A[i])
for i in range(len(A)-1):
    M = max(A[i+1:len(A)])
    if (M-A[i]) == b:
        for j in range(i+1,len(A)):
            if b == A[j] - A[i]:
                Nc += 1
print(Nc)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int,input().split())
A = list(map(int,input().split()))
b = 0
Nc = 0
for i in range(len(A)):
    for j in range(i+1,len(A)):
        b = max(b,A[j]-A[i])
for i in range(len(A)):
    for j in range(i+1,len(A)):
        if b == A[j] - A[i]:
            Nc += 1

print(Nc)

Submission status: Time Limit Exceeded

Solution code:
#D    高橋君と見えざる手 / An Invisible Hand
N,T = [int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
Max = 0
count = 1
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        temp = A[i]-A[j]
        if temp>Max:
            Max = temp
            count = 1
        elif temp==Max:
            count +=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
#D    高橋君と見えざる手 / An Invisible Hand
N,T = [int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
Max = 1
count = 0
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        if (A[i]-A[j])>Max:
            Max = A[i]-A[j]
            count = 1
        elif (A[i]-A[j])==Max:
            count +=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))

l = 0
r = max(A)
m = (r + l) // 2

def cal(N, T, A):
    return max([A[i] - min(A[:i]) for i in range(1,len(A))]) * T // 2

ans = 0
m = cal(N, T, A)
mini = A[0]
for i in range(1, N):
    mini = min((mini, A[i]))
    if m == (A[i] - mini) * T // 2:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))

l = 0
r = max(A)
m = (r + l) // 2

def cal(N, T, A):
    return max([A[i] - min(A[:i]) for i in range(1,len(A))]) * T // 2

ans = 0
m = cal(N, T, A)
for i in range(1, N):
    if m == (A[i] - min(A[:i])) * T // 2:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
raw_input('').split()
A = [int(x) for x in raw_input('').split()]
max = 0
msp = A[0]
for i in range(0,len(A)-1):
  if msp <= A[i]:
    continue
  else:
    msp = A[i]
    for j in range(i+1,len(A)):
        pf_t = A[j] - A[i]
        if pf_t > max:
          max = pf_t
          spot = [(i,j)]
        elif pf_t == max:
          spot.append((i,j))
print len(spot)

Submission status: Time Limit Exceeded

Solution code:
N,T = [int(x) for x in raw_input('').split()]
A = [int(x) for x in raw_input('').split()]
max = 0
for i in range(0,len(A)):
  for j in range(i+1,len(A)):
      pf_t = A[j] - A[i]
      if pf_t > max:
        max = pf_t
        spot = [(i,j)]
      elif pf_t == max:
        spot.append((i,j))
print len(spot)

Submission status: Time Limit Exceeded

Solution code:
N=int(input().split(" ")[0])
put=input().split(" ")
A=[]
for i in range(N):
    A.append(int(put[i]))

p=[A[0]]
for i in range(1,N-1):
    if A[i-1]<A[i] and A[i]>A[i+1]:
        p.append(A[i])
    elif A[i-1]>A[i] and A[i]<A[i+1]:
        p.append(A[i])

p.append(A[N-1])

x=0
t=1
for i in range(len(p)):
    k=i+1
    y=0
    while k<=(len(p)-1):
        if y< p[k]-p[i]:
            y=p[k]-p[i]
        k+=1
    if x<y:
        x=y
        t=1
    elif x==y:
        t=t+1

print(t)

Submission status: Time Limit Exceeded

Solution code:
N=int(input().split(" ")[0])
A=input().split(" ")
x=0
t=1
for i in range(N):
    k=i+1
    y=0
    while k<=N-1:
        if y< int(A[k])-int(A[i]):
            y=int(A[k])-int(A[i])
        k+=1
    if x<y:
        x=y
        t=1
    elif x==y:
        t=t+1

print(t)

Submission status: Time Limit Exceeded

Solution code:
N=int(input().split(" ")[0])
A=input().split(" ")
x=[]
for i in range(N):
    k=i+1
    y=0
    while k<=N-1:
        if y< int(A[k])-int(A[i]):
            y=int(A[k])-int(A[i])
        k+=1
    if y!=0:    
        x.append(y)


print(x.count(max(x)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input().split(" ")[0])
A=input().split(" ")
x=[]
for i in range(N):
    k=i+1
    y=0
    while k<=N-1:
        if y< int(A[k])-int(A[i]):
            y=int(A[k])-int(A[i])
        k+=1
    if y!=0:    
        x.append(y)

x.sort()

print(x.count(x[-1]))

Submission status: Time Limit Exceeded

Solution code:
N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]


mx = -1e10
cnt = 0

for i in range(len(A)-1):
	if max(A[i+1:]) - A[i] > mx:
		mx = max(A[i+1:]) - A[i]
		cnt = 1

	elif max(A[i+1:]) - A[i] == mx:
		cnt += 1

print cnt

Submission status: Time Limit Exceeded

Solution code:
N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]


mx = -1e10
cnt = 0

for i in range(len(A)-1):
	if max(A[i+1:]) - A[i] > mx:
		mx = max(A[i+1:]) - A[i]
		cnt = 1

	elif max(A[i+1:]) - A[i] == mx:
		cnt += 1

print cnt

Submission status: Time Limit Exceeded

Solution code:
N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]

mx = -1e10
cnt = 0

for i in range(len(A)-1):
	for j in range(i + 1, len(A)):
		if A[j] - A[i] > mx:
			mx = A[j] - A[i]
			cnt = 1

		elif A[j] - A[i] == mx:
			cnt += 1

print cnt

Submission status: Time Limit Exceeded

Solution code:
N,T = [int(x) for x in input().split()]
prices = [int(x) for x in input().split()]

diffmax = 0
c = 0
for i,priceA in enumerate(prices):
    if i == len(prices) - 1: continue

    m = max(prices[i+1:])
    if m - priceA > diffmax:
        diffmax = m - priceA
        c = prices[i+1:].count(m)
    elif m - priceA == diffmax:
        c += prices[i+1:].count(m)
print(c)

Submission status: Time Limit Exceeded

Solution code:
N,T = [int(x) for x in input().split()]
prices = [int(x) for x in input().split()]

diffmax = 0
count = 0
for i,priceA in enumerate(prices):
    for priceB in prices[i+1:]:
        diff = priceB - priceA
        if diffmax < diff:
            diffmax = diff
            count = 1
        elif diffmax == diff:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, T= list(map(int, input().split()))
A = [int(x) for x in input().strip().split()]

result = []

for i in range(N - 1):
    if max(A[i+1:]) - A[i] < 0:
        continue
    else:
        result.extend([x - A[i] for x in A[i+1:] if x>A[i]])

print(result.count(max(result)))

Submission status: Time Limit Exceeded

Solution code:
N, T = input().strip().split()
N = int(N)
A = [int(x) for x in input().strip().split()]

result = []

for i in range(N - 1):
    counter = 0
    result.extend([x - A[i] for x in A[i+1:] if x>A[i]])
    counter += 1

print(result.count(max(result)))

Submission status: Time Limit Exceeded

Solution code:
N, T = input().strip().split()
N = int(N)
A = [int(x) for x in input().strip().split()]

result = []
for i in range(N - 1):
    counter = 0
    for x in A[i+1:]:
        if x > A[i] and counter+i < N:
            result.append(x - A[i])
        counter += 1

print(result.count(max(result)))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N,T=[int(x) for x in input().split()]
towns=list([int(x) for x in input().split()])

com=combinations(range(0,N),2)

bene=[]
for c in com:
    bene.append(towns[c[1]]-towns[c[0]])

max_bene=max(bene)
print(len([x for x in bene if x==max_bene]))

Submission status: Time Limit Exceeded

Solution code:
N,T=list(map(int,input().split()))
towns=list(map(int,input().split()))

BSList=[]

for offset in range(0,N):
    d={"B":offset,"S":max(range(offset,N),\
                                      key=lambda x:towns[x])}
    d["D"]=towns[d["S"]]-towns[d["B"]]
    BSList+=[d] if d["D"]>0 else []

max_bene=max([x["D"] for x in BSList])
BSList=[x for x in BSList if x["D"]==max_bene]

print(len(BSList))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N,T=map(int,raw_input().split())
A=map(int,raw_input().split())

arrmaxv=[]
arrmaxc=[]
for i in xrange(N-1):
    a=A[i:]
    maxv=max(a)
    maxc=a.count(maxv)
    arrmaxv.append((maxv-A[i]))
    arrmaxc.append(maxc)

maxv=np.array(arrmaxv)
maxc=np.array(arrmaxc)
idx=np.argwhere(maxv==np.max(maxv))
cnt=maxc[idx]
print(np.sum(cnt))

Submission status: Time Limit Exceeded

Solution code:
n, t = (int(i) for i in input().split())
price = [int(i) for i in input().split()]

def get_min(tr_list,end_indx):
    return min(tr_list[:end_indx])

profit = [0 for i in range(n-1)]
for i in range(n-1):
    profit[i] = price[i+1] - get_min(price,i+1)
#print("profit",profit)
max_profit = max(profit)
#print("max_profit",max_profit)
result = profit.count(max_profit)
print(result)

Submission status: Time Limit Exceeded

Solution code:
N,_=map(int,raw_input().split())
A=map(int,raw_input().split())
difflist=[A[i]-A[j] for i in range(0,len(A)) for j in range(0,len(A)) if i>j]
print len([1 for x in difflist if x==max(difflist)])

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
mins = [min(a[:i + 1]) for i in range(n - 1)]
count = 0
sa = [a[i] - mins[i - 1] for i in range(1, n)]
max_sa = max(sa)
count = 0

for i in range(n - 1):
    if sa[i] == max_sa:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,t=map(int,input().split())
a=[int(i) for i in input().split()]
v=[0]*(n-1)
for i in range(n-1):
    v[i]=max(a[i+1:])-a[i]
print(v.count(max(v)))

Submission status: Time Limit Exceeded

Solution code:
n,t=map(int,input().split())
a=[int(i) for i in input().split()]
v=[0]*(n-1)
for i in range(n-1):
    x=0
    for j in range(i+1,n):
        if a[j]-a[i]>=x:
            x=a[j]-a[i]
    v[i]=x
print(v.count(max(v)))

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
am = 0
cnt =1
for i in range(n-1) : 
    if max(a[i+1:]) -a[i] == am:
        cnt += 1
    elif max(a[i+1:])-a[i]>am:
        am= max(a[i+1:]) -a[i]
        cnt =1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * (n-1) 
li = [0] * (n-1) 
for i in range(n-1) : 
    l[i]= max(a[i+1:]) -a[i] 
print(l.count(max(l)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, T = map(int, raw_input().split())
arr = np.array(map(int, raw_input().split()))
res = np.max(arr) - arr[0]
max_res = 0
path = []

for i in range(1, arr.shape[0]-1):
    res = np.max(arr[i+1:])
    end_here = np.where(arr[i+1:]==res)[0]

    if res == max_res:
        for e in end_here:
            path.append((i, e))

    if res > max_res:
        max_res = res
        for e in end_here:
            path.append((i, e))

result_dict_a = {}
result_dict_b = {}
for a, b in path:
    result_dict_s[a] = result_dict_s.get(a, 0) + 1
    result_dict_e[b] = result_dict_e.get(b, 0) + 1

print np.min(np.array(result_dict_a.values().extend(result_dict_e.values())))

Submission status: Time Limit Exceeded

Solution code:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

#for i in range(len(inp)):
i=0
c = []
for j in range(i+1,len(inp)):
    #if inp[i]<inp[j]:
    c.append(inp[j]-inp[i])
#check.append(c)
check=c
checkMax.append(max(check))

while (len(check)>1):
    check.pop(0)
    checkMax.append(max(check))


for j in range(1,len(inp)):
    checkMax[j-1] += inp[0]-inp[j]

#print (check)
#print (checkMax)
print (checkMax.count(max(checkMax)))

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * (n-1) 
li = [0] * (n-1) 
for i in range(n-1) : 
    l[i]= max(a[i+1:]) -a[i] 
    li[i] = i+1+a[i+1:].index(max(a[i+1:]))
s = [li[i] for i, x in enumerate(l) if x == max(l)] 
print(len(set(s)))

Submission status: Time Limit Exceeded

Solution code:
def profits(arr):
    result = []
    for i in range(len(arr)-1):
        result.append(max(max(arr[i+1:]) - arr[i], 0))
    return result



if __name__ == '__main__':
    [N, T] = [int(i) for i in raw_input().split(' ')]
    costs = [int(i) for i in raw_input().split(' ')]

    pro = profits(costs)
    m = max(pro)
    print(pro.count(m))

Submission status: Time Limit Exceeded

Solution code:
def read():
	return [int(i) for i in input().split(' ')]
N, T = read()
A = read()
expect = 0
route = set()
length = len(A)
for i in range(length):
	buy = A[i]
	for j in range(i + 1, length):
		benefit = A[j] - buy
		if(benefit > expect):
			expect = benefit
			route = set([i, j])
		elif(benefit == expect):
			if(i not in route and j not in route):
				route.add(i)
				route.add(j)
cost = len(route) >> 1
print(cost)

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, raw_input().split())
l = map(int, raw_input().split())

gap = 0
num = 0

for i in range(n):
    for j in range(i+1, n):
        temp = l[j] - l[i]
        if temp > gap:
            gap = temp
            num = 1
        elif temp == gap:
            num += 1
print num

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * (n-1) 
li = [0] * (n-1) 
for i in range(n-1) : 
    l[i]= max(a[i+1:]) -a[i] 
    li[i] = i+1+a[i+1:].index(max(a[i+1:]))
maxl = [i for i, x in enumerate(l) if x == max(l)] 
s=set() 
for i in maxl:
    s.add(li[i]) 
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
N,T = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
M = []
for i in range(0,len(A)):
    M.append(max(list(map(lambda x:x-A[i], A[i:]))))
ix = [i for i,j in enumerate(M) if j == max(M)]
print(len(ix))

Submission status: Time Limit Exceeded

Solution code:
N, T = list(map(int, input().split()))
A = list(map(int, input().split()))

benefit = -1
cost = 1

for i in range(N - 1):
    for j in range(i + 1, N):
        if benefit == A[j] - A[i]:
            cost += 1
        if benefit < A[j] - A[i]:
            cost = 1
            benefit = A[j] - A[i]

print(cost)

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int ,raw_input().split())
li = map(int , raw_input().split())

ans = 1
temp = 0
for i in range(len(li)):
	for j in range(i+1,len(li)):
		if(li[j] - li[i] == temp):
			ans += 1
		elif(li[j] - li[i] > temp):
			temp = li[j] - li[i]
			ans = 1

print ans

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
num_list = input().split()
num_list = [int(x) for x in num_list]

dif = 0
count = 0

for index, i in enumerate(num_list):
    for j in num_list[index:]:
   #     print(j)
        if j > i and (j - i) >= dif:
            dif = j - i

for index, i in enumerate(num_list):
    for j in num_list[index:]:
        if j - i == dif:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N, T = map(int, raw_input().split())

A = map(int, raw_input().split())
A.append(0)

sa = 0
ans = 0

for i in xrange(N):
    sa = max(sa, max(A[i+1:N+1]) - A[i])

for i in xrange(N):
    if sa == max(A[i+1:N+1]) - A[i]:
        ans += 1

print ans

Submission status: Time Limit Exceeded

Solution code:

a, b = map(int, raw_input().split())
x = map(int, raw_input().split())
s = 0
M = 0
c = 0
while True:
    if len(x) == 0:
        break
    m = max(x)
    t = x.index(max(x))
    if 0 != t:
        mi = min(x[0:t])
    else:
        mi = m+1
    if M < m-mi:
        M = m-mi
        c = 1
    elif M == m-mi:
        c += 1
    x = x[t+1:]
print c

Submission status: Time Limit Exceeded

Solution code:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

for i in range(len(inp)):
    c = [0]
    for j in range(i+1,len(inp)):
        if inp[i]<inp[j]:
            c.append(inp[j]-inp[i])
    check.append(c)
    checkMax.append(max(c))

#print (check)
#print (checkMax)
print (checkMax.count(max(checkMax)))

Submission status: Time Limit Exceeded

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

N, T = list(map(int, input().split()))
A = list(map(int, input().split()))

p, q = 0, 0
for i in range(N):
	for j in range(i+1, N):
		d = A[j] - A[i]
		if d > p:
			p = d
			q = 1
		elif d == p:
			q += 1

print(q)

Submission status: Time Limit Exceeded

Solution code:
input()
a=[]
for i in input().split():
	a.append(int(i))

maxp = 0
b=[]
for i in range(len(a)):
	for j in range(len(a))[i+1:]:
		d=a[j]-a[i]
		if d>maxp:
			maxp=d
		b.append(d)
c=0
for i in b:
	if i==maxp:
		c+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

submax = 0
total = 0
for i in range(N):
    for j in range(i+1,N):
        sub = A[j]-A[i]
        if sub == submax:
            total += 1
        if sub > submax:
            total = 1
            submax = sub

print(total)

Submission status: Time Limit Exceeded

Solution code:
input()
a=[]
for i in input().split():
	a.append(int(i))

maxp = 0
for i in range(len(a)):
	for j in range(len(a))[i+1:]:
		if a[j]-a[i]>maxp:
			maxp=a[j]-a[i]

c=0
for i in range(len(a)):
	for j in range(len(a))[i+1:]:
		if a[j]-a[i]==maxp:
			c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
dat = raw_input()
(N,T) = dat.split(" ")

N = int(N)
T = int(T)

dat = raw_input()
A = map(int,dat.split(" "))

diffmax = 0
diffno = 0

for x in range(0,len(A)-1):
  d = max(A[x+1:]) - A[x]
  if d > diffmax:
    diffmax = d
    diffno = 1
  elif d == diffmax:
    diffno += 1

print diffno

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


a, b = map(int, raw_input().split())
x = map(int, raw_input().split())
c = Counter()

k = 0
for j in range(len(x)):
    c += Counter([x[i] - x[i-j] if x[i]-x[i-j] > 0 else 0 for i in range(j, len(x))])
m = 0
m = sorted(c.items(), key=lambda x: x[0], reverse=True)[0][1]
print m

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N, T = map(int, raw_input().split())

A = map(int, raw_input().split())

sa = 0
ans = 0

for i in xrange(N):
    for j in xrange(i+1, N):
        sa = max(sa, A[j] - A[i])

#print sa

for i in xrange(N):
    for j in xrange(i+1, N):
        if sa == A[j] - A[i]:
            ans += 1

print ans

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, T = map(int, readline().split())
    A = list(map(int, readline().split()))

    L = []
    Max = 0
    Min = A[0]

    for i in range(1, N):
        if A[i] < Min:
            Min = A[i]
        if A[i] - Min > Max:
            Max = A[i] - Min
        L.append(A[i] - Min)
    print(L.count(Max))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    min_A = float('inf')
    cnt = 0
    profit = 0
    for i in range(N):
        min_A = min(min_A,A[i])
        diff_A = A[i] - min_A
        if profit == diff_A:
            cnt += 1
        elif profit < diff_A:
            cnt = 1
            profit = diff_A
    print(cnt)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
A = list(map(int,input().split()))
b = float('inf')
B = []
for a in A:
    b = min(b,a)
    B.append(a-b)
B.sort()
cnt = B.count(B[-1])
print(cnt)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
count = 0
l = []
max = 0
min = a[0]
for i in range(1,n):
    if a[i] < min:
        min = a[i]
    if a[i] - min > max:
        max = a[i] - min
    l.append(a[i] - min)
print(l.count(max))

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = [int(x) for x in input().split()]
lst = [0]
mina = a[0]
for i in range(1, n):
    mina = min(mina, a[i-1])
    lst.append(max(0, a[i]-mina))

lst.sort(reverse=True)
cnt = 1
for i in range(1, n):
    if lst[0] == lst[i]: cnt += 1
    else: break

print(cnt)

Submission status: Accepted

Solution code:
n, t = map(int,input().split())
a = list(map(int,input().split()))
amax = [a[-1]] * n

for i in range(n-2, -1, -1):
    amax[i] = max(amax[i+1], a[i])

cnt = 0
v = -10**10
for i in range(n-1):
    b = amax[i+1] - a[i]
    if b > v:
        v = b
        cnt = 1
    elif b == v:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1 for i in range(self.n + 1)]
        self.finv = [1 for i in range(self.n + 1)]
        for i in range(2, self.n+1):
            self.fac[i] = (self.fac[i - 1] * i) % self.mod
            self.finv[i] = (self.finv[i - 1] * pow(i, -1, self.mod)) % self.mod

    def comb(self, n, m):
        return self.fac[n] * (self.finv[n - m] * self.finv[m] % self.mod) % self.mod
        
def iparse():
    return list(map(int, input().split()))

def RLE(s):
    res = []
    prev = ""
    cnt = 0
    for e in s:
        if prev == "":
            prev = e
            cnt += 1
        elif prev == e:
            cnt += 1
        else:
            res.append((cnt,prev))
            prev = e
            cnt = 1
    res.append((cnt,prev))
    return res


if __name__ == "__main__":
    n, t = iparse()
    a = iparse()
    a.reverse()
    s = [0 for i in range(n + 1)]
    for i in range(n):
        s[i + 1] = max(s[i], a[i])
    
    res = []
    a.reverse()
    for i in range(n):
        res.append(s[n - 1 - i] - a[i])
    res.sort()
    res.reverse()
    cnt = 1
    prev = res[0]
    for i in range(1,n):
        if prev == res[i]:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
dictA = {}
minA = 10**13
maxD = 0
for ai in A:
    minA = min(minA, ai)
    maxD = max(ai-minA, maxD)
    dictA[ai] = True
ans = 0
for ai in A:
    dictA[ai] = False
    if dictA.get(ai + maxD, False):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))

min_num = 10 ** 9 + 7
diff = 0
count = 0
for i in range(N):
    min_num = min(min_num, A[i])
    if diff == A[i] - min_num:
        count += 1
    elif A[i] - min_num > diff:
        count = 1
        diff = A[i] - min_num
    else:
        continue

print(count)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
Max = [0] * N
revenue = 0
for i in range(N)[::-1]:
    if i == N-1:
        Max[i] = (A[i], 1)
        continue
    ma, cnt = Max[i+1]
    if ma > A[i]:
        Max[i] = Max[i+1]
    elif ma == A[i]:
        Max[i] = (ma, cnt + 1)
    else:
        Max[i] = (A[i], 1)
    revenue = max(revenue, Max[i][0] - A[i])

D = dict()

for a, (m, c) in zip(A, Max):
    if m - a == revenue:
        if (m, a) in D:
            x, y = D[(m, a)]
            D[(m, a)] = (x + 1, max(y, c))
        else:
            D[(m, a)] = (1, c)

ans = 0
for key, value in D.items():
    x, y = value
    ans += min(x, y)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n,t=MI()
	A=LI()

	B=[A[0]]
	for i in A[1:]:
		B.append(min(B[-1],i))
	#print(B)

	C=[0]*n

	for i in range(n):
		C[i]=A[i]-B[i]

	c=max(C)
	print(C.count(c))

	
	



	
	
	









if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    cost = [0]*N# cost[i]: i番目で買ってから最適に売ることで得られる利益
    q = []
    heappush(q,-A[N-1])
    for i in range(N-2,-1,-1):
        v = heappop(q)
        cost[i] = -v-A[i]
        heappush(q,v)
        heappush(q,-A[i])
    # print(cost)
    print(cost.count(max(cost)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    M = [0] * (N - 1) + [A[-1]]
    for i in range(N - 2, -1, -1):
        M[i] = max(M[i + 1], A[i])
    cnt = 0
    maxA = 0
    for a, m in zip(A, M):
        if maxA < m - a:
            maxA = m - a
            cnt = 1
        elif maxA == m - a:
            cnt += 1
    print(cnt)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
A = tuple(map(int, input().split()))
count = 0
maxdiff = 0
mina = 10**9+1
for a in A:
    mina = min(mina, a)
    diff = a - mina
    if diff > maxdiff:
        count = 1
        maxdiff = diff
    elif diff == maxdiff:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
A = tuple(map(int, input().split()))
AI = [(i, a) for i, a in enumerate(A)]
AI = sorted(AI, key=lambda x: x[1])

# 小さい順に見ていく
count = 0
maxdiff = 0
visited = [0] * n
for i, a in AI:
    if visited[i]:
        continue
    visited[i] = 1

    for j in range(i+1, n):
        if visited[j]:
            break
        visited[j] = 1
        diff = A[j] - a
        if diff > maxdiff:
            count = 1
            maxdiff = diff
        elif diff == maxdiff:
            count += 1
print(count)