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:
import numpy as np

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

difDict = {}
sell = np.max(A)
for buy in range(N - 1):
    if A[buy] == sell:
        sell = np.max(A[buy+1:])

    profit = sell - A[buy]
    if profit in difDict:
        difDict[profit] += 1
    else:
        difDict[profit] = 1

key = max(difDict.keys())
print(min(difDict[key], int(T / 2)))

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")

difDict = {}
sell = max(A)
for buy in range(N - 1):
    if A[buy] == sell:
        sell = max(A[buy+1:])

    profit = sell - A[buy]
    if profit in difDict:
        difDict[profit] += 1
    else:
        difDict[profit] = 1

key = max(difDict.keys())
print(min(difDict[key], int(T / 2)))

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")

difDict = {}
for buy in range(N - 1):
    sell = max(A[buy+1:])
    profit = sell - A[buy]
    sell_num = np.sum(A[buy+1:] == sell)
    if profit in difDict:
        difDict[profit] += sell_num
    else:
        difDict[profit] = sell_num

key = max(difDict.keys())
print(difDict[key])

Submission status: Time Limit Exceeded

Solution code:
n=int(input().split()[0])
s=input().split()
l=[0 for i in range(n)]
m=[0 for i in range(n)]
M=[0 for i in range(n)]
for i in range(n):
  l[i]=int(s[i])
m[0]=l[0]
M[0]=l[-1]
for i in range(1,n):
  m[i]=min(m[i-1],l[i])
  M[i]=max(M[i-1],l[-i-1])
M.reverse()
d=[M[i]-m[i] for i in range(n)]
ma=max(d)
l=[]
for i in range(n):
  if d[i]==ma:
    if m[i] not in l:
      l.append(m[i])
print(len(l))

Submission status: Time Limit Exceeded

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

cost_list = list(map(int, input().split()))

max_num = 0
max_profit = 0

for i in range(len(cost_list)-1):
    profits = [x - cost_list[i] for x in cost_list[i+1 :]]
    M_profit = max(profits)

    if max_profit < M_profit:
        max_num = 1
        max_profit = M_profit

    elif max_profit == M_profit:
        max_num += 1

print(max_num)

Submission status: Time Limit Exceeded

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

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

d = -1
cnt, ans = 0, 1
for i in range(N - 1):
    l = A[i]
    r = max(A[i + 1:])
    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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)


class Segtree():
    INT_MIN=-10**9

    def __init__(self,size):
        self.size=1
        while self.size<size:
            self.size=self.size*2
        self.node=[self.INT_MIN]*(2*self.size-1)


    def update(self,k,a):
        k+=self.size-1
        self.node[k]=a
        while k>0:
            k=(k-1)/2
            self.node[k]=max(self.node[k*2+1],self.node[k*2+2])

    def get_max(self,queryL,queryR,k=0,nodeL=0,nodeR=-1):
        if nodeR==-1:nodeR=self.size
        if (nodeR<=queryL or queryR<=nodeL):return self.INT_MIN
        if (queryL<=nodeL and nodeR<=queryR):return self.node[k]
        else:
            nodeM=(nodeL+nodeR)/2
            vl=self.get_max(queryL,queryR,k*2+1,nodeL,nodeM)
            vr=self.get_max(queryL,queryR,k*2+2,nodeM,nodeR)
            return max(vl,vr)
            
n,t=map(int,raw_input().split())
a=map(int,raw_input().split())
seg=Segtree(n)
for i in xrange(n):
    seg.update(i,a[i])
ans=0
mx=0
for i in xrange(n):
    tmp=seg.get_max(i,n)-a[i]
    if mx<tmp:
        ans=1
        mx=tmp
    elif mx==tmp:
        ans+=1
print ans

Submission status: Time Limit Exceeded

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

maxDiff = 0
count = 0
nextMax = 0
checkMode = True
nextMaxIdx = 0
for i in range(0, N):

    if(checkMode):
        nextMax = 0
        for j in range(i, N):
            if(nextMax <= A[j]):
                nextMax = A[j]
                nextMaxIdx = j

    diff = nextMax - A[i]

    if(maxDiff == diff):
        count += 1
    if(maxDiff < diff):
        maxDiff = diff
        count = 1

    if(i == j):
        checkMode = True


print count

Submission status: Time Limit Exceeded

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


maxDiff = 0
count = 0
for i in range(0, N):
    for j in range(i, N):
        diff = A[j] - A[i]
        if(maxDiff == diff):
            count += 1
        if(maxDiff < diff):
            maxDiff = diff
            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())

min_first = 0
max_first = 0
diffs = []

for i in range(0,len(A)-1):
    min_first = min(A[0:i+1])
    max_first = max(A[i+1:len(A)])
    diff = max_first - min_first
    diffs.append(diff)

def count(arr):
    max_value = max(arr)
    last_value = -1
    cnt = 0
    for a in arr:
        if a == max_value and a != last_value:
            cnt += 1
        last_value = a
    return cnt

print count(diffs)
# 出力

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestFunc(unittest.TestCase):
    def test_1(self):
        self.assertEqual(fun(5,8,[50,30,40,10,20]),2)
        self.assertEqual(fun(3,2,[100,50,200]),1)
        self.assertEqual(fun(10,100,[7,10,4,5,9,3,6,8,2,1]),2)
        self.assertEqual(fun(5,2,[1,2,3,2,4]),1)




def fun(n,t,a):
    aa = []
    b = None
    s = None
    for i in range(n):
        m = -1
        for j in range(i+1,n):
            if a[j]>a[i] and a[j]-a[i]>m:
                m = a[j]-a[i]
        if m>0:
            aa.append(m)

    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

    return ans


if __name__=='__main__':
    #unittest.main()                                                                                                                                                              

    n,t = [int(x) for x in raw_input().split(" ")]
    a = [int(x) for x in raw_input().split(" ")]
    print(fun(n,t,a))

Submission status: Time Limit Exceeded

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

s1=input()
s2=input()
town_num,apple_num=(int(_) for _ in s1.split(" "))
apple_price=[int(i) for i in s2.split(" ")]
apple_buy_num=apple_num//2

loop1 = 0
benefit=0
max_benefit=0
max_benefit_num=0
max_price=0
for p in apple_price:
    loop1+=1
    loop2=0
    max_price=0
    for i in apple_price:
        loop2+=1
        if loop1 < loop2 and max_price < i :
            max_price = i

    if max_price-p > max_benefit:
        max_benefit=max_price-p
        max_benefit_num=1
    elif max_price-p == max_benefit:
        max_benefit_num+=1

print(max_benefit_num)

Submission status: Time Limit Exceeded

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

s1=input()
s2=input()
town_num,apple_num=(int(_) for _ in s1.split(" "))
apple_price=[int(i) for i in s2.split(" ")]
apple_buy_num=apple_num//2

loop1 = 0
benefit=0
max_benefit=0
max_benefit_num=0
for p in apple_price:
    loop1+=1
    loop2=0
    list = []
    for i in apple_price:
        loop2+=1
        if loop1 < loop2 :
            list.append(int(i))
    if list==[]:
        break
    elif max(list)-p > max_benefit:
        max_benefit=max(list)-p
        max_benefit_num=1
    elif max(list)-p == max_benefit:
        max_benefit_num+=1
print(max_benefit_num)

Submission status: Time Limit Exceeded

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

max_profit = A_n[1] - A_n[0]
min_element = min(A_n[0], A_n[1])
for i in xrange(1, len(A_n)):
    if A_n[i] - min_element > max_profit:
        max_profit = A_n[i] - min_element
    if A_n[i] < min_element:
        min_element = A_n[i]

count = 0
for j in xrange(0, len(A_n)):
    if (A_n[j] + max_profit) in A_n[j:]:
        count += 1

print count

Submission status: Time Limit Exceeded

Solution code:
import collections

input()
a = [int(x) for x in input().split()]
print(max(collections.Counter([max(a[i + 1:]) - x for i, x in enumerate(a[:-1])]).items())[1])

Submission status: Time Limit Exceeded

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

max_profit = 0
cost = 0
for i in xrange(len(A_n)):
    for j in xrange(i, len(A_n)):
        if A_n[j]-A_n[i] > max_profit:
            max_profit = A_n[j]-A_n[i]

for i in xrange(len(A_n)):
    for j in xrange(i, len(A_n)):
        if A_n[j]-A_n[i] == max_profit:
            cost += 1

print cost

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, raw_input().split())
a = map(int, raw_input().split())
max = -1
count = 0
start = a[0]
for i in xrange(len(a)):
    for j in xrange(i, len(a)):
        dis = a[j] - a[i]
        if dis > max:
            max = dis
            count = 1
        elif dis == max:
            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()]
d = [max(a[i:]) - a[i] for i in range(N-1)]
ans = d.count(max(d))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
l = input()
N,T = int(l.split()[0]), int(l.split()[1])
Ais = [int(x) for x in input().split()]
count = 0
maxdiff = 0
for ind, i in enumerate(Ais):
    for j in Ais[ind:]:
        if j-i > maxdiff:
            maxdiff = j-i
            count=1
        elif j-i == maxdiff:
            count+=1
print (count)

Submission status: Time Limit Exceeded

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
        s.append(0)
    if s[len(s)-1] < i - x:
        s[len(s)-1] = i - x
c = 0
for i in s:
    if i == max(s):
        c+=1
print(min(c,t//2))

Submission status: Time Limit Exceeded

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

import collections


def solve(n, t, xs):
    trades = collections.defaultdict(int)
    for i in range(n):
        for j in range(i + 1, n):
            delta = xs[j] - xs[i]
            if delta > 0:
                trades[delta] += 1
    max_delta = max(trades.keys())
    return trades[max_delta]


def main():
    n, t = map(int, input().split())
    xs = list(map(int, input().split()))
    print(solve(n, t, xs))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a = [int(i) for i in raw_input().split()]

good = []

for i in range(len(a)-1):
    good.append(max(a[i+1:])-a[i])

m = max(good)

count = 0

for g in good:
    if g==m:count+=1

print count

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys
n,t = ma()
A = lma()
INF=10**15

mns = [INF]*(n+1) ##mxs[i] :: max(A[i:n])
for i in range(n):
    mns[i] = min(mns[i-1],A[i])
c = 0
dmx = -1
for i in range(1,n):
    if A[i]-mns[i] >dmx:
        dmx=A[i]-mns[i]
        c=1
    elif A[i]-mns[i] ==dmx:
        c+=1
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, T = MAP()
A = LIST()

buy = [0]*N
sell = [0]*N
buy_memo = [0]*N
sell_memo = [0]*N

tmp_buy = INF
tmp_buy_memo = -1
for i in range(N):
	if A[i] <= tmp_buy:
		tmp_buy = A[i]
		tmp_buy_memo = i
	buy[i] = tmp_buy
	buy_memo[i] = tmp_buy_memo

tmp_sell = 0
tmp_sell_memo = -1
for i in range(N-1, -1, -1):
	if tmp_sell <= A[i]:
		tmp_sell = A[i]
		tmp_sell_memo = i
	sell[i] = tmp_sell
	sell_memo[i] = tmp_sell_memo

diff = [sell[i]-buy[i] for i in range(N)]
max_diff = max(diff)

buy_possible = [0]*N
sell_possible = [0]*N

for i in range(N):
	if diff[i] == max_diff:
		buy_possible[buy_memo[i]] = 1
		sell_possible[sell_memo[i]] = 1

print(min(sum(buy_possible), sum(sell_possible)))

Submission status: Accepted

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

import bisect

n, t = map(int, input().split())
a = list(map(int, input().split()))
mx = 0
p = [0] * n
for i in range(n-1,-1,-1):
    mx = max(mx, a[i])
    p[i] = mx - a[i]
p.sort()
print(n-bisect.bisect_left(p, p[-1]))

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
ar=list(map(int,input().split()))
mn=float('inf')
mdif,mxc=-float('inf'),0
for e in ar:
    if(e-mn>mdif):
        mdif=e-mn
        mxc=1
    elif(e-mn==mdif):
        mxc+=1
    mn=min(mn,e)
print(mxc)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = [int(x) for x in input().split()]
mx = [0] * n
mx[-1] = a[-1]
for i in range(n - 2, -1, -1):
  mx[i] = max(mx[i + 1], a[i])
d = 0
c = 0
for i in range(n - 1):
  cur = a[i]
  can = mx[i + 1]
  dd = can - cur
  if dd > d:
    d = dd
    c = 1
  elif dd == d:
    c += 1
print(c)

Submission status: Accepted

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

n,r,*a = map(int,read().split())


high = a[-1]
delta = -1

for ai in a[::-1]:
    if high < ai:
        high = ai
    if high-ai > delta:
        delta = high-ai

#from collections import Counter
#d = Counter()

high = a[-1]

hs = 0
ls = 0

ans = 0
for ai in a[::-1]:
    if high < ai:
        high = ai
        hs = 1
        ans += min(hs,ls)
        ls = 0
    elif high == ai:
        hs += 1        
    
    if high - ai == delta:
        ls += 1
    

print(ans+min(hs,ls))

Submission status: Accepted

Solution code:
def main():

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

    if N == 1: return 0

    min_v = A[0]
    max_d = float('-inf')
    for i in range(1, N):
        if A[i] - min_v > max_d:
             max_d = A[i] - min_v
        if A[i] < min_v:
            min_v =  A[i]

    d = set()
    d.add(A[0])
    ans = 0
    for i in range(1, N):
        if A[i] - max_d in d: ans += 1
        d.add(A[i])
    return ans



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, T = map(int, input().split())
A = list(map(int, input().split()))
min_acc = [A[0]]

for i in range(1, N):
    min_acc.append(min(min_acc[-1], A[i]))
    
M = 0

for i in range(1, N):
    M = max(M, A[i]-min_acc[i-1])

ans = 0

for i in range(1, N):
    if A[i]-min_acc[i-1]==M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
a=list(map(int,input().split()))
max_profit=0
mini=a[0]
for i in range(1,N):
    max_profit=max(max_profit,a[i]-mini)
    mini=min(mini,a[i])
#print(max_profit)
mini=a[0]
ans=0
for i in range(1,N):
    if a[i]-mini==max_profit:
        ans+=1
    mini=min(mini,a[i])
print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = map(int, input().split())
mxx, mnx = 0, 10**18
for a in A:
    if a-mnx > mxx:
        c, mxx = 1, a-mnx
    elif a-mnx == mxx:
        c += 1
    mnx = min(mnx, a)
print(c)

Submission status: Accepted

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

m = 10 ** 9
L = [m] * (N)


for i in range(0,N):
  if A[i] <= m:
    m = A[i]
  L[i] = A[i] - m

M = max(L)

print(L.count(M))

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
A=list(map(int,input().split())) # 0-indexed
B=[0 for i in range(N)] # B[i]~B[N-1]のmax
Bl=[set() for i in range(N)] # B[i]~B[N-1]のmaxとなるB[j]の添字jのリスト
B[N-1]=A[N-1]
Bl[N-1].add(N-1)
for i in range(N-2,-1,-1):
    if A[i]>B[i+1]:
        B[i]=A[i]
        Bl[i].add(i)
    elif A[i]==B[i+1]:
        B[i]=B[i+1]
        Bl[i]=Bl[i+1]+{i}
    elif A[i]<B[i+1]:
        B[i]=B[i+1]
        Bl[i]=Bl[i+1]

C=[B[i]-A[i] for i in range(N)]
'''
print(A)
print(B)
print(Bl)
print(C)
'''
Cm=max(C)
Cml=set()
for i in range(N):
    if C[i]==Cm:
        Cml.update(Bl[i])
'''
print(Cm)
print(Cml)
'''
ans=len(Cml)

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = tuple(map(int, input().split()))
mini = 10**10
bnf = 0
cnt = 1
for i in range(N):
	mini = min(mini, A[i])
	_bnf = A[i] - mini
	if _bnf > bnf:
		bnf = _bnf
		cnt = 1
	elif _bnf == bnf:
		cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, T = map(int, input().split())
a = list(map(int, input().split()))
cm = [float("inf")] * (N + 1)
cmx = [0] * (N + 1)
for i in range(N):
  cm[i + 1] = min(cm[i], a[i])
  cmx[N - 1 - i] = max(cmx[N - i], a[N - 1 - i])
res = 0
x = 0
for i in range(N + 1):
  x = max(cmx[i] - cm[i], x)
for i in range(N):
  if cmx[i] - a[i] == x:
    res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

N, T = map(int, readline().split())
A = list(map(int, readline().split()))
Amax = [None]*N
Amax[N-1] = A[N-1]
for i in range(N-2, -1, -1):
    Amax[i] = max(Amax[i+1], A[i])

B = [am - a for a, am in zip(A, Amax)]
print(Counter(B)[max(B)])

Submission status: Accepted

Solution code:
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    tmp = A[-1]
    diff_A = [0] * N
    for i in range(N-1,-1,-1):
        tmp = max(A[i],tmp)
        diff_A[i] = tmp - A[i]

    print(diff_A.count(max(diff_A)))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

B = [0]*N
C = [0]*N

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

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

B = B[:-1]
C = C[1:]
D = list(map(lambda x:C[x]-B[x],range(N-1)))
t = max(D)

s = 0
D.append(0)
for i in range(N-1):
    if D[i] == t and D[i] > D[i+1]:
        s += 1

print(s)

Submission status: Accepted

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

h = []
B = [0]*N

for i in range(N):
    h.append(A[i])
    h = [min(h)]
    B[i] = h[0]

j = []
C = [0]*N

for i in range(N-1,-1,-1):
    j.append(A[i])
    j = [max(j)]
    C[i] = j[0]

B = B[:-1]
C = C[1:]
D = list(map(lambda x:C[x]-B[x],range(N-1)))
t = max(D)

s = 0
D.append(0)
for i in range(N-1):
    if D[i] == t and D[i] > D[i+1]:
        s += 1

print(s)

Submission status: Accepted

Solution code:
import heapq

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

h = []
B = [0]*N

for i in range(N):
    heapq.heappush(h,A[i])
    B[i] = h[0]

j = []
C = [0]*N

for i in range(N-1,-1,-1):
    heapq.heappush(j,-A[i])
    C[i] = -j[0]

B = B[:-1]
C = C[1:]
D = list(map(lambda x:C[x]-B[x],range(N-1)))
t = max(D)

s = 0
D.append(0)
for i in range(N-1):
    if D[i] == t and D[i] > D[i+1]:
        s += 1

print(s)

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.array(list(map(int,input().split())))

B = np.minimum.accumulate(A)

C = A - B

ans = (C == C.max()).sum()

print(ans)

Submission status: Accepted

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:
        ans += 1
print(ans)

Submission status: Accepted

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(cnt)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
m=10**10
M=0
k=[]
for i in range(n):
	m=min(m,a[i])
	M=a[i]-m
	k.append(M)
o=max(k)
print(k.count(o))

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

#受け取り
N, T = getlist()
A = getlist()
m = A[0]
plus = -float("inf")
cost = 1
for i in range(1, N):
	if A[i] - m == plus:
		cost += 1
	elif A[i] - m > plus:
		plus = A[i] - m
		cost = 1
	else:
		pass
	m = min(m, A[i])

print(cost)

Submission status: Accepted

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()))
    d = collections.defaultdict(list)
    min_b = 10 ** 9
    max_p = 0
    for v in a:
        p = v - min_b
        max_p = max(max_p, p)
        d[p] += [min_b]
        min_b = min(min_b, v)
    print(len(d[max_p]))


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
_,_,*a=map(int,open(0).read().split());d={}
for x,y in zip(a,__import__("itertools").accumulate(a,min)):d[x-y]=d.get(x-y,0)+1
print(d[max(d.keys())])

Submission status: Accepted

Solution code:
from itertools import*;_,a=open(0);*a,=map(int,a.split());c=[x-y for x,y in zip(a,accumulate(a,min))];print(c.count(max(c)))

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    MAXl = [A[-1]]
    for i in range(1,N-1):
        MAXl.append(max(MAXl[i-1],A[-i-1]))
    MAXl.reverse()
    count = 0
    profit = 0
    for i in range(N-1):
        p = MAXl[i]-A[i]
        if p == profit:
            count += 1
        elif p > profit:
            profit = p
            count = 1

    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

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(len(collections.Counter(b[1])))


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
# ARC063D - 高橋君と見えざる手 / An Invisible Hand (ABC047D)
def main():
    N, T, *A = map(int, open(0).read().split())
    cur, cand = A[0], []
    for i in A:
        if i < cur:  # buy at the most inexpensive place
            cur = i
        else:
            cand += [i - cur]  # sell at higher places
    x = max(cand)  # the highest profits
    # count the number of pairs which produce x
    ans = sum(i == x for i in cand)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 = len(pairs)
print(ans)

Submission status: Accepted

Solution code:
(N,T)=map(int,input().split())
a=list(map(int,input().split()))
x=10**9
d=0
counter=0
for i in a:
    if i<x:
        x=i
    elif i-x>d:
        d=i-x
        counter=1
    elif i-x==d:
        counter+=1
print(counter)

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
A=list(map(int,input().split()))
x=10**9
d=0
ans=0
for a in A:
    if a<x:
        x=a
    elif a-x>d:
        d=a-x
        ans=1
    elif a-x==d:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
a = list(map(int,input().split()))
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+1] < mn:
        mn = a[i+1]
if len(l) > 0:
    d = max(l)
ans = l.count(d)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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(count)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
A=[int(i) for i in input().split()]
A=A[::-1]
B,C=[0]*n,[0]*n
B[0]=A[0]
cur=A[0]
for i in range(1,n):
  cur=max(cur,A[i])
  B[i]+=cur
for i in range(n):
  C[i]=B[i]-A[i]
m=max(C)
ans=0
for i in range(n):
  if C[i]==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, t = li()
a = list(li())

mina = [0]*n
mina[0] = a[0]
maxprof = 0

for i in range(1, n):
    mina[i] = min(mina[i-1], a[i])

ans = 0
for i in range(n):
    if a[i] - mina[i] > maxprof:
        maxprof = a[i] - mina[i]
        ans = 1

    elif a[i] - mina[i] == maxprof:
        ans += 1

print(ans)

Submission status: Accepted

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

b = float('inf')

c = 0

ans = 0

for i in range(n):
    if a[i]<b:
        b = a[i]
    if a[i]-b == c:
        ans += 1
    elif a[i]-b > c:
        c = a[i]-b
        ans = 1

print(ans)