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: Wrong Answer

Solution code:
from collections import defaultdict

n, t = map(int, input().split())
a = list(map(int, input().split()))

buy, sell = a[0], a[0]
gain = defaultdict(int)
for ai in a:
    if buy > ai:
        buy, sell = ai, ai
    sell = max(sell, ai)
    gain[sell - buy] += 1
print(gain[max(gain)])

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
mi = a[0]
ma = a[0]
ans = 0
dif = 0
temp1 = 0
temp3 = 0
for i in range(1, n):
  if a[i]>ma:
    ma=a[i]
  elif a[i]==ma:
    temp1+=1
  elif a[i]==mi:
    temp3+=1
  elif a[i]<mi:
    temp2 = ma-mi
    mi=a[i]
    ma=0
    if temp2>dif:
      dif = temp2
      ans = 1+min(temp1, temp3)
      temp1=0
      temp3=0
    elif temp2==dif:
      ans += 1+min(temp1, temp3)
      temp1 = 0
      temp3=0
    else:
      temp1 = 0
      temp3=0
  #print("ma " + str(ma) )
  #print("mi " + str(mi) )
  #print("temp1 " + str(temp1))
  #print("ans " + str(ans))
  #print("dif " + str(dif))
  #print(" ")
temp2 = ma-mi
if temp2>dif:
  dif = temp2
  ans = 1+min(temp3,temp1)
  temp1=0
elif temp2==dif:
  ans += 1+min(temp1, temp3)
  temp1 = 0
else:
  temp1 = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
mi = a[0]
ma = a[0]
ans = 0
dif = 0
temp1 = 0
for i in range(1, n):
  if a[i]>ma:
    ma=a[i]
  elif a[i]==ma:
    temp1+=1
  elif a[i]<mi:
    temp2 = ma-mi
    mi=a[i]
    ma=0
    if temp2>dif:
      dif = temp2
      ans = 1+temp1
      temp1=0
    elif temp2==dif:
      ans += 1+temp1
      temp1 = 0
    else:
      temp1 = 0
  #print("ma " + str(ma) )
  #print("mi " + str(mi) )
  #print("temp1 " + str(temp1))
  #print("ans " + str(ans))
  #print("dif " + str(dif))
  #print(" ")
temp2 = ma-mi
if temp2>dif:
  dif = temp2
  ans = 1+temp1
  temp1=0
elif temp2==dif:
  ans += 1+temp1
  temp1 = 0
else:
  temp1 = 0
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n, t = map(int, input().split())
a = list(map(int, input().split()))
b = [a[-1]] * n
for i in range(n-2,-1,-1):
    b[i] = min(b[i+1], a[i])
print(b)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n, t = map(int, input().split())
a = list(map(int, input().split()))
#ret = []
ret = 0
st = 0
stc = 1
prc = 0
prev = a[0]
mx = 0
for i, b in enumerate(a[1:]):
    if b >= prev:
        if st == b:
            stc += 1
        if b == prev:
            prc += 1
        else:
            prc = 1
        prev = b
    else:
        prev = b
        if st != i:
            if mx == a[i]-a[st]:
#                ret.append([a[i]-a[st], min(stc, prc)])
                ret += min(stc, prc)
            elif mx < a[i]-a[st]:
#                ret = []
#                ret.append([a[i]-a[st], min(stc, prc)])
                ret = min(stc, prc)
                mx = a[i]-a[st]
#            ret.append([st, i, stc, prc])
        st = i+1
        stc = 1
        prc = 0
if st!=n-1 and mx <= a[-1]-a[st]:
    if mx == a[-1]-a[st]:
        ret += min(stc, prc)
#        ret.append([a[-1]-a[st], min(stc, prc)])
    elif mx < a[-1]-a[st]:
        ret = min(stc, prc)
#        ret = [a[-1]-a[st], min(stc, prc)]
#    ret.append([st,n-1, stc, prc])


print(ret)

Submission status: Wrong Answer

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

A = list(map(int,input().split())) + [-1]

mi = A[0]
ma = A[0]
b = []
for i in range(1,N+1) :
    if ma < A[i] :
        ma = A[i]
    else :
        b.append(ma-mi)
        mi = A[i]
        ma = A[i]
a = b.count(max(b))
print(a)

Submission status: Wrong Answer

Solution code:
N, T = map(int,input().split())
A = list(map(int,input().split()))
B = [0 for k in range(N)]
B[0] = A[0]
for k in range(1,N):
    B[k] = min(B[k-1],A[k])
m = 0
for k in range(N):
    m = max(A[k]-B[k],m)
ans = 0
for k in range(N):
    if A[k]-B[k] == m and T >= 2:
        ans += 1
        T -= 2
print(ans)

Submission status: Wrong Answer

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

cnt = max_profit = 0
INF = float('inf')
min_cost = INF
for a in A:
    profit = a - min_cost
    if profit == max_profit:
        cnt += 1
    elif profit > max_profit:
        cnt = 1
        max_profit = profit
    min_cost = min(min_cost, a)

print(min(cnt,T//2))

Submission status: Wrong Answer

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, t = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    b = collections.defaultdict(list)
    m_c = 10 ** 9
    for i, v in enumerate(a):
        if i != 0 and m_c < v:
            b[v-m_c] += [m_c]
        m_c = min(m_c, v)
    b = sorted(b.items(), reverse=True)[0]
    print(b)
    print(len(collections.Counter(b[1])))


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
*A, = map(int, input().split())
max_price = A[N-1]
max_prof = 0
count = 1
for a in reversed(A[:N-1]):
    prof = max_price - a
    if prof < 0: max_price = a
    elif prof == max_prof: count += 1
    elif prof > max_prof: max_prof = prof; count = 1;
print(min(count, T//2))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
*A, = map(int, input().split())
max_price = A[N-1]
max_prof = 0
count = 0
for a in reversed(A[:N-1]):
    prof = max_price - a
    if prof < 0: max_price = a
    elif prof == max_prof: count += 1
    elif prof > max_prof: max_prof = prof; count = 1;
print(min(count, T//2))

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
alist = list(map(int, input().split()))
minal = [alist[0]]
maxal = [alist[-1]]
for a in alist[1:]:
  if minal[-1] > a:
    minal.append(a)
  else:
    minal.append(minal[-1])

for a in alist[::-1][1:]:
  if maxal[-1] < a:
    maxal.append(a)
  else:
    maxal.append(maxal[-1])
maxal = maxal[::-1]

maxda = 0
ans = 0
prevmina, prevmaxa = None, None
for mina, maxa in zip(minal, maxal):
  if prevmina == mina and prevmaxa == maxa:
    continue
  elif maxa - mina == maxda:
    ans += 1
  elif maxa - mina > maxda:
    maxda = maxa - mina
    ans = 1
  prevmina, prevmaxa = mina, maxa

print(min(ans, t))

Submission status: Wrong Answer

Solution code:
f = lambda: map(int,input().split())
n,_ = f()
a = list(f())
a.append(0)
ans = 0
d = 0
pa = 0
m = a[0]
for i in a:
    if i < pa:
        if d == pa-m:
            ans += 1
        elif d < pa-m:
            d = pa-m
            ans = 1
        m = i
    pa = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
s=input().split()
if s[0]=="2":
  print("1")
  sys.exit(0)
s=input().split()
l=[]
for i in range(1,len(s)):
  l.append(int(s[i])-int(s[i-1]))
l.sort()
m=l[-1]
for i in range(2,len(s)):
  if l[-i]!=m:
    print(i-1)
    sys.exit(0)
print(i)

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

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

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

d = -1
cnt, ans = 1, 1
l = A[0]
for i in range(1, N):
    l = min(l, A[i - 1])
    r = A[i]
    if l < r:
        if r - l == d:
            cnt += 1
            ans = max(ans, cnt)
        else:
            cnt = 1
            d = max(d, r - l)

print(ans)

Submission status: Wrong Answer

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

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

d = -1
cnt, ans = 1, 1
l = A[0]
for i in range(1, N):
    l = min(l, A[i - 1])
    r = A[i]
    if l < r:
        if r - l == d:
            cnt += 1
            ans = max(ans, cnt)
        else:
            cnt = 1
            d = max(d, r - l)

print(min(ans, T))

Submission status: Wrong Answer

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

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

d = -1
cnt, ans = 1, 1
l = A[0]
for i in range(1, N):
    l = min(l, A[i - 1])
    r = A[i]
    if l <= r:
        if r - l == d:
            cnt += 1
            ans = max(ans, cnt)
        else:
            cnt = 1
            d = max(d, r - l)

print(ans)

Submission status: Wrong Answer

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

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

d = -1
cnt, ans = 0, 1
l = A[0]
for i in range(1, N):
    l = min(l, A[i - 1])
    r = A[i]
    if l <= r:
        if r - l == d:
            cnt += 1
            ans = max(ans, cnt)
        else:
            cnt = 1
            d = max(d, r - l)

print(ans)

Submission status: Wrong Answer

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

X = [0]*N
for i in xrange(N - 2, -1, -1):
    X[i] = max(X[i + 1], A[i + 1])

mx, cnt = 0, 0
for i, a in enumerate(A):
    tmp = X[i]
    if tmp - a > mx:
        mx = tmp - a
	cnt = 1
    elif tmp - a == mx:
        cnt += 1
print min(cnt, T)

Submission status: Wrong Answer

Solution code:
n,t = [int(x) for x in raw_input().split(" ")]
a = [int(x) for x in raw_input().split(" ")]

aa = []
b = None
s = None
for i in range(n):
    if b!=None:
        if s==None:
            if b<a[i]:
                s = a[i]
            else:
                b = a[i]
        elif s<=a[i]:
            s = a[i]
        elif s>b:
            aa.append(s-b)
            b = a[i]
            s = None
    else:
        b = a[i]

if b!=None and s!= None and s-b>0:
    aa.append(s-b)

c = aa[0]
ans = 1
for i in range(1,len(aa)):
    if c<aa[i]:
        c = aa[i]
        ans = 1
    elif c==aa[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

mi = [0] * N
mx = [0] * N

mi[0] = A[0]
for i in range(1, N):
    mi[i] = min(A[i], mi[i-1])

mx[N-2] = A[N-2]
for i in range(N-2, -1, -1):
    mx[i] = max(A[i], mx[i+1])

gap = 0
for i in range(N):
    gap = max(gap, mx[i] - mi[i])

pvmx = 0
pvmi = 0
count = 0
for i in range(N):
    if mx[i] - mi[i] == gap and (pvmx, pvmi) != (mx[i], mi[i]):
        count += 1
    pvmx, pvmi = mx[i], mi[i]

print(count)

Submission status: Wrong Answer

Solution code:

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

maxdif = 0
maxdifcnt=0
prevmin = A[0]
prevmincnt=0

for i in range(N):
        if A[i]==prevmin:
                prevmincnt += 1
        elif A[i]<prevmin:
                prevmin=A[i]
                prevmincnt = 1

        if A[i]-prevmin>maxdif:
                maxdif=A[i]-prevmin
                maxdifcnt=prevmincnt
                prevmincnt=0
        elif A[i]-prevmin == maxdif:
                maxdifcnt += 1

print(maxdifcnt)

Submission status: Wrong Answer

Solution code:
import collections

input()
a = [int(x) for x in input().split()]

lowest = 9999
diff = -1
diffcnt = 0
for x in a:
    if diff == x - lowest:
        diffcnt += 1
    elif diff < x - lowest:
        diffcnt = 1
        diff = x - lowest

    lowest = min(lowest, x)

print(diffcnt)

Submission status: Wrong Answer

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

mx = 0
mt = 0
c = 0
x = a[0]
a = a[1:]
for i in a:
    if i < x:
        x = i
        if mx == mt:
            c += 1
        elif mx < mt:
            mx = mt
            c = 1
        mt = 0
    elif mt < i - x:
        mt = i - x
if mt == mx:
    c+=1
print(c)

Submission status: Wrong Answer

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

mx = 0
mt = 0
c = 0
x = a[0]
a = a[1:]
for i in a:
    if i < x:
        x = i
        if mx == mt:
            c += 1
        elif mx < mt:
            mx = mt
            c = 1
        mt = 0
    elif mt < i - x:
        mt = i - x
if mt == mx:
    c+=1
print(min(c,t//2))

Submission status: Wrong Answer

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

s = [0]
x = a[0]
a = a[1:]
for i in a:
    if i < x:
        x = i
        if max(s) == s[len(s)-1]:
            if len(s)>1 and max(s) > s[len(s)-2]:
                s = [s[len(s)-1]]
            s.append(0)
        else:
            s[len(s)-1]=0
    elif s[len(s)-1] < i - x:
        s[len(s)-1] = i - x
if max(s) == s[len(s)-1]:
    print(min(len(s),t//2))
else:
    print(min(len(s)-1,t//2))

Submission status: Wrong Answer

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

s = [0]
x = a[0]
a = a[1:]
for i in a:
    if i < x:
        x = i
        if max(s) == s[len(s)-1]:
            if len(s)>1 and max(s) > s[len(s)-2]:
                s = [s[len(s)-1]]
            s.append(0)
        else:
            s[len(s)-1]=0
        continue
    if s[len(s)-1] < i - x:
        s[len(s)-1] = i - x
print(min(len(s),t//2))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
highestCount = [1]

for price in prices[-2:-N-1:-1]:
    if price==highestTally[-1]:
        highestCount.append(highestCount[-1]+1)
    else:
        highestCount.append(1)
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()
highestCount.reverse()

indexOfHighest={}
for i in range(N-1,-1,-1):
    if highestTally[i]==prices[i]:
        indexOfHighest[highestTally[i]]=i

biggestJump=0
sellingPriceForBiggestJump=0
HPcount=0
LPcount=0
HPGroups=[]
LPGroups=[]
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    #print(jump,bestSellingPrice,biggestJump)
    if jump>biggestJump:
        biggestJump = jump
        #LPcount+=1
        LPGroups=[]
        HPGroups=[]
        
        LPGroups.append(1)
        sellingPriceForBiggestJump = bestSellingPrice
        #HPcount=highestCount[indexOfHighest[bestSellingPrice]]
        HPGroups.append(highestCount[indexOfHighest[bestSellingPrice]])
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            #HPcount+=highestCount[indexOfHighest[bestSellingPrice]]
            HPGroups.append(highestCount[indexOfHighest[bestSellingPrice]])
            LPGroups.append(0)
        LPGroups[-1]+=1
count = 0
for a,b in zip(HPGroups,LPGroups):
    count+=min(a,b)
if T//2>=count:
    print(count)
else:
    print(int(T//2))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
highestCount = [1]

for price in prices[-2:-N-1:-1]:
    if price==highestTally[-1]:
        highestCount.append(highestCount[-1]+1)
    else:
        highestCount.append(1)
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()
highestCount.reverse()

indexOfHighest={}
for i in range(N-1,-1,-1):
    if highestTally[i]==prices[i]:
        indexOfHighest[highestTally[i]]=i

biggestJump=0
sellingPriceForBiggestJump=0
HPcount=0
LPcount=0
HPGroups=[]
LPGroups=[]
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    #print(jump,bestSellingPrice,biggestJump)
    if jump>biggestJump:
        biggestJump = jump
        #LPcount+=1
        LPGroups.append(1)
        sellingPriceForBiggestJump = bestSellingPrice
        #HPcount=highestCount[indexOfHighest[bestSellingPrice]]
        HPGroups.append(highestCount[indexOfHighest[bestSellingPrice]])
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            #HPcount+=highestCount[indexOfHighest[bestSellingPrice]]
            HPGroups.append(highestCount[indexOfHighest[bestSellingPrice]])
            LPGroups.append(0)
        LPGroups[-1]+=1
count = 0
for a,b in zip(HPGroups,LPGroups):
    count+=min(a,b)
if T//2>=count:
    print(count)
else:
    print(int(T//2))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
highestCount = [1]
 
for price in prices[-2:-N-1:-1]:
    if price==highestTally[-1]:
        highestCount.append(highestCount[-1]+1)
    else:
        highestCount.append(1)
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()
highestCount.reverse()
 
indexOfHighest={}
for i in range(N-1,-1,-1):
    if highestTally[i]==prices[i]:
        indexOfHighest[highestTally[i]]=i
 
biggestJump=0
sellingPriceForBiggestJump=0
HPcount=0
LPcount=0
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    #print(jump,bestSellingPrice,biggestJump)
    if jump>biggestJump:
        biggestJump = jump
        LPcount=1
        sellingPriceForBiggestJump = bestSellingPrice
        HPcount=highestCount[indexOfHighest[bestSellingPrice]]
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            HPcount+=highestCount[indexOfHighest[bestSellingPrice]]
        LPcount+=1
count = min(LPcount,HPcount)            
if T//2>=count:
    print(count)
else:
    print(int(T//2))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
highestCount = [1]

for price in prices[-2:-N-1:-1]:
    if price==highestTally[-1]:
        highestCount.append(highestCount[-1]+1)
    else:
        highestCount.append(1)
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()
highestCount.reverse()

indexOfHighest={}
for i in range(N-1,-1,-1):
    if highestTally[i]==prices[i]:
        indexOfHighest[highestTally[i]]=i

biggestJump=0
sellingPriceForBiggestJump=0
HPcount=0
LPcount=0
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    #print(jump,bestSellingPrice,biggestJump)
    if jump>biggestJump:
        biggestJump = jump
        LPcount+=1
        sellingPriceForBiggestJump = bestSellingPrice
        HPcount=highestCount[indexOfHighest[bestSellingPrice]]
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            HPcount+=highestCount[indexOfHighest[bestSellingPrice]]
        LPcount+=1
count = min(LPcount,HPcount)            
if T//2>=count:
    print(count)
else:
    print(int(T//2))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
highestCount = [1]

for price in prices[-2:-N-1:-1]:
    if price==highestTally[-1]:
        highestCount.append(highestCount[-1]+1)
    else:
        highestCount.append(1)
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()
highestCount.reverse()

indexOfHighest={}
for i in range(N-1,-1,-1):
    if highestTally[i]==prices[i]:
        indexOfHighest[highestTally[i]]=i

biggestJump=0
sellingPriceForBiggestJump=0
count=0
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    #print(jump,bestSellingPrice,biggestJump)
    if jump>biggestJump:
        biggestJump = jump
        sellingPriceForBiggestJump = bestSellingPrice
        count=highestCount[indexOfHighest[bestSellingPrice]]
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            count+=highestCount[indexOfHighest[bestSellingPrice]]
            
if T//2>=count:
    print(count)
else:
    print(int(T//2))

Submission status: Wrong Answer

Solution code:
n, t = map(int, raw_input().split())
prices = list(map(int, raw_input().split()))
lows = n * [ 0 ]
low_counts = n * [ 0 ]
low = prices[0] + 1
low_count = 1
for i, x in enumerate(prices):
    if x == low:
        low_count += 1
    elif x < low:
        low = x
        low_count = 1
    lows[i] = x
    low_counts[i] = low_count
best_gap = 0
best_gap_count = 1
high = prices[-1] - 1
high_count = 1
for i in range(len(prices) - 1, 0, -1):
    x = prices[i]
    if x == high:
        high_count += 1
    elif x > high:
        high = x
        high_count = 1
    gap = high - lows[i - 1]
    gap_count = min(high_count, low_counts[i - 1])
    if gap == best_gap:
        if gap_count == best_gap_count:
            best_gap_count += gap_count
        elif gap_count > best_gap_count:
            best_gap_count = gap_count
    elif gap > best_gap:
        best_gap = gap
        best_gap_count = gap_count
print(best_gap_count)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
for price in prices[-2:-N-1:-1]:
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()

biggestJump=0
sellingPriceForBiggestJump=0
count=0
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    if jump>biggestJump:
        biggestJump = jump
        sellingPriceForBiggestJump = bestSellingPrice
        count=1
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            count+=1
            
if T//2>=count:
    print(count)
else:
    print(int(T//2))

Submission status: Wrong Answer

Solution code:
n, t = map(int, raw_input().split())
a = map(int, raw_input().split())
max = -1
now_max = 0
count = 1
start = a[0]
for i in xrange(len(a)):
    if a[i] == start:
        continue
    elif a[i] < start:
        if now_max < max:
            pass
        elif now_max == max:
            count += 1
        else:
            max = now_max
            count == 1
        start = a[i]
        now_max = 0
    else:
        now_max += a[i] - a[i - 1]
if now_max == max:
    count += 1
elif now_max > max:
    count = 1

print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
N,T = map(int,input().split())
prices = list(map(int,input().split()))
last = 10000000000
highestTally = [prices[-1]]
for price in prices[-2:-N-1:-1]:
    highestTally.append(max(highestTally[-1],price))
highestTally.reverse()

biggestJump=0
sellingPriceForBiggestJump=0
count=0
for index,price in enumerate(prices):
    if index==N-1:
        break
    bestSellingPrice = highestTally[index+1]
    jump = bestSellingPrice-price
    if jump>biggestJump:
        biggestJump = jump
        sellingPriceForBiggestJump = bestSellingPrice
        count=1
    elif jump==biggestJump:
        if bestSellingPrice!=sellingPriceForBiggestJump:
            sellingPriceForBiggestJump = bestSellingPrice
            count+=1
print(int(min(count,T//2)))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
L = []
tmp = []
for i in range(N):
    if i == 0:
        tmp.append(A[i])
    else:
        if A[i] >= A[i-1]:
            tmp.append(A[i])
        else:
            L.append(tmp)
            tmp = [A[i]]
L.append(tmp)
M = []
for l in L:
    len_l = len(l)
    if len_l != 1:
        M.append(l[-1] - l[0])
max_m = max(M)
ans = 0
for m in M:
    if m == max_m:
        ans += 1
if ans == 0:
    ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = []
for i in range(a-1):
    br.append(max(ar[i+1:a]) - ar[i])
print(br.count(max(br)))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = []
cr = [0]
for i,r in enumerate(ar):
    if i != 0:
        if r - min(br) > max(cr):
            cr.clear()
            cr.append(r - min(br))
        elif r - min(br) == max(cr):
            cr.append(r - min(br))
    br.append(r)
print(len(cr))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = [0]
for i in range(a-1):
    cr = ar[i+1:a]
    if max(cr) - ar[i] > max(br):
        br.clear()
        br.append(max(cr) - ar[i])
    elif max(cr) - ar[i] == max(br):
        br.append(max(cr) - ar[i])
print(len(br))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

maxA = [0 for _ in range(N + 1)]
minA = [float('inf') for _ in range(N + 1)]

for i, a in enumerate(A):
    minA[i + 1] = min(minA[i], a)
for i, a in enumerate(reversed(A)):
    maxA[-1 - i] = max(maxA[-1 - (i - 1)], a)

maxProfit = 0
for i in range(1, N):
    if maxProfit < maxA[i + 1] - minA[i]:
        maxProfit = maxA[i + 1] - minA[i]

pairs = set([])
for i in range(1, N):
    if maxProfit == maxA[i + 1] - minA[i]:
        pairs.add((minA[i], maxA[i + 1]))

ans = 0
for minVal, maxVal in pairs:
    right = N - 1
    maxCount = 0
    while A[right] != maxVal:
        right -= 1
    for i in range(right):
        if A[i] == minVal:
            maxCount += 1
    left = 0
    minCount = 0
    while A[left] != minVal:
        left += 1
    for i in range(left, N):
        if A[i] == maxVal:
            minCount += 1
    ans += min(maxCount, minCount)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

max_income = 0
ans = 0
for i in range(N-1):
    buy = towns[i]
    sell = max(towns[i+1:])
    earn = sell-buy
    if max_income == earn:
        ans += 1
    elif max_income < earn:
        max_income = earn
        ans = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = []
if b <= 3:
    print(1)
else:
    for i in range(a-1):
        br.append(max(ar[i+1:a])-ar[i])
    cr = sorted(br,reverse=True)
    if br.count(cr[0]) == 1:
        print(1)
    else:
        print(min(br.count(cr[0]),b//2))

Submission status: Time Limit Exceeded

Solution code:
N,T=map(int,input().split())
A=list(map(int,input().split()))
i=0
j=1
a=0
b=0
while i<=N-1:
    if j==N:
        i+=1
        j=i+1
    elif A[i]>A[j]:
        i=j
        j+=1
    else:
        if A[j]-A[i]>a:
            a=A[j]-A[i]
            b=1
            j+=1
        elif A[j]-A[i]==a:
            b+=1
            j+=1
        elif A[j]-A[i]<a:
            j+=1
print(b)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, T = np.array(input().split(), dtype="int")
A = np.array(input().split(), dtype="int")

sell = np.max(A)
max_profit = 0
ans = 0
for buy in range(N - 1):
    if A[buy] == sell:
        sell = np.max(A[buy+1:])

    profit = sell - A[buy]
    if profit > max_profit:
        max_profit = profit
        ans = 1
    elif profit == max_profit:
        ans += 1

print(min(ans, int(T / 2)))