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: Accepted

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

a = map(int, input().split(" "))

INF = 1000000000000

max_price = -1
min_price = -1

min_pos = 1
max_pos = 1
max_diff = 0
tmp = INF
ans = 0

for c in a:
    if max_price < 0 or min_price < 0:
        max_price = c
        min_price = c
        continue

    if max_price == c:
        max_pos += 1
        tmp = min(tmp, min_pos, max_pos)

    if min_price == c:
        min_pos += 1

    if max_price < c:
        max_price = c
        max_pos = 1

        if max_diff == max_price - min_price:
            tmp = min(tmp, min_pos, max_pos)

        elif max_diff < max_price - min_price:
            max_diff = max_price - min_price
            ans = 0
            tmp = min(tmp, min_pos, max_pos)

    if min_price > c:
        min_price = c
        max_price = c
        min_pos = 1
        ans += (tmp if tmp < INF else 0)
        tmp = INF

if tmp < INF:
    ans += tmp

print(ans)

Submission status: Accepted

Solution code:
n,t = map(int, input().split( ))
a = list(map(int, input().split( )))
mn = 10**10
mx = 0
cnt_mn = 0#現在の買値の最小値
cnt_inf = 0#最大りえきの達成で買える町の数
cnt_sup = 0#現在の最大利益の達成で売れる町の数
for i in range(n):
    if a[i]<mn:
        mn = a[i]
        cnt_mn = 1
    elif a[i] == cnt_mn:
        cnt_mn += 1
    if mx < a[i] - mn:
        mx = a[i] - mn
        cnt_sup = 1
        cnt_inf = cnt_mn
    elif mx == a[i]-mn:
        cnt_sup += 1
        cnt_inf += cnt_mn

print(min(cnt_inf,cnt_sup))

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
A=list(map(int,input().split()))
a=10**10
b=0
c=0
ans=0
for i in range(n):
  if A[i]<a:
    a=A[i]
    b=0
  if A[i]>b:
    b=A[i]
    if b-a>c:
      c=b-a
      ans=0
    elif b-a==c:
      ans=ans+1
print(ans+1)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
import sys
input = sys.stdin.readline

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

    maxgain = 0
    time = 0
    maxcost = A[0]
    mincost = A[0]

    for now in A:
        # print(now)
        maxcost = max(maxcost,now)
        mincost = min(mincost,now)
        temp = now - mincost
        # print(temp)
        if maxgain == temp:
            time += 1
        elif maxgain < temp:
            maxgain = temp
            time = 1
        # print(maxgain)
        # print(time)

    print(time)



main()

Submission status: Accepted

Solution code:
import numpy as np
N,T = map(int,input().split())
A=np.array(input().split(),dtype=np.int32)
s=A-np.minimum.accumulate(A)
print((s==max(s)).sum())

Submission status: Accepted

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

Submission status: Accepted

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

im = 0
m = 10**20
B = []
C = []
for i,a in enumerate(A):
    if a<m:
        m=a
        im=i
    B.append(a-m)
    C.append(im)

maxB = max(B)
print(len({c for b,c in zip(B,C) if b==maxB}))

Submission status: Accepted

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

bl = []

min_a = float("inf")
for a in al:
   min_a = min(a, min_a)
   bl.append(min_a)

cl = []

for a,b in zip(al, bl):
   cl.append(a-b)

cl = sorted(cl)

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

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
m = A[0]
B = []
for i in range(1, N):
    m = min(m, A[i-1])
    B.append(A[i]-m)

M = max(B)
print(B.count(M))

Submission status: Accepted

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

mini = 10**9+1
diff = 0
ans = 1
for i in range(n):
    if a[i] <= mini:
        mini = a[i]

    if diff == a[i] - mini:
        ans += 1
    elif diff < a[i] - mini:
        ans = 1
        diff = a[i] - mini
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, T = rl()
A = np.array(rl())
A_cummin = np.minimum.accumulate(A)
B = A - A_cummin

answer = (B == B.max()).sum()
print(answer)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, T = rl()
A = rl()
answer = 1
profit = 0
min = A[0]
for i in range(1, N):
    if A[i] < min:
        min = A[i]
        continue
    x = A[i] - min
    if x > profit:
        answer = 1
        profit = x
    elif x == profit:
        answer += 1

print(answer)
# 40

Submission status: Accepted

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

INF = 10**10
L_min = [INF] * N
for i in range(N):
  L_min[i] = min(L_min[i-1], A[i])
#print(L_min)

P_max = -1
for i in range(N):
  P_max = max(P_max, A[i] - L_min[i])
#print(P_max)

answer = 0
for i in range(N):
  if P_max == A[i] - L_min[i]:
    answer += 1
print(answer)

Submission status: Accepted

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

# 準備
N0 = 2 ** (N - 1).bit_length()
data = [float('inf')] * (2 * N0)

# a_k の値を x に更新
def update(k, x):
    k += N0 - 1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2 * k + 1], data[2 * k + 2])

# [a_l, a_(l+1), ..., a_(r-1)]の最小値を求める
def query(l, r):
    L = l + N0
    R = r + N0
    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R - 1])

        if L & 1:
            s = min(s, data[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s


# まずupdate()を使ってa_kの値を更新
for i in range(len(a)):
    update(i, -a[i])

from collections import defaultdict
dic = defaultdict(int)
for L in range(1, N):
    d = -a[L - 1] - query(L, N)
    if d > 0:
        dic[d] += 1

print(dic[sorted(dic.keys())[-1]])

Submission status: Accepted

Solution code:
inf = float('inf')

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

cm = [inf] * N
m = inf
for i, a in enumerate(A):
    m = min(m, a)
    cm[i] = m

cM = [-inf] * N
M = -inf
for i, a in enumerate(A[::-1]):
    M = max(M, a)
    cM[i] = M
cM.reverse()

diff = 0
for m, M in zip(cm, cM):
    diff = max(diff, M - m)

ans = 0
for a, M in zip(A, cM):
    if a + diff <= M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, t = LI()
A = LI()
min_ret = A[0]
max_diff = 1
for i in range(1, n):
    max_diff = max(max_diff, A[i] - min_ret)
    min_ret = min(min_ret, A[i])



ans = 0
min_ret = A[0]
for j in range(1, n):
    if A[j] - min_ret == max_diff:
        ans += 1
    min_ret = min(min_ret, A[j])


print(ans)

Submission status: Accepted

Solution code:
import sys

n, t, *a = map(int, sys.stdin.read().split())

def main():
    r = 0
    cnt = 0
    prof = 0
    max_prof = 0
    buy_price = sell_price = a[0]
    while True:
        r += 1
        if r == n:
            if prof == max_prof:
                cnt += 1
            elif prof > max_prof:
                max_prof = prof
                cnt = 1
            break

        cur = a[r]
        if cur > sell_price:
            sell_price = cur
            prof = sell_price - buy_price
        elif cur > buy_price:
            pass
        else:
            if prof == max_prof:
                cnt += 1
            elif prof > max_prof:
                max_prof = prof
                cnt = 1
            buy_price = sell_price = cur
            prof = 0

    return cnt

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

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
lmin=[a[0]]
rmax=[a[-1]]
for i in range(1,n):
  if a[i]<=lmin[-1]:
    lmin.append(a[i])
  else:
    lmin.append(lmin[-1])
  if a[-i-1]>=rmax[-1]:
    rmax.append(a[-i-1])
  else:
    rmax.append(rmax[-1])
mxls=[rmax[-i-2]-lmin[i] for i in range(n-1)]
mxls.append(-10**18)
ans=0
mx=max(mxls)
for i in range(n-1):
  if mxls[i]==mx and mxls[i]!=mxls[i+1]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, T = map(int,input().split())
A = list(map(int,input().split()))
max_profit = [0]
Min = A[0]
for i in range(N-1):
  if A[i] < Min:
    Min = A[i]
  if A[i+1] - Min > max_profit[0]:
    max_profit = [A[i+1] - Min]
  elif A[i+1] - Min == max_profit[0]:
    max_profit.append(A[i+1] - Min)
print(len(max_profit))

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))

Submission status: Accepted

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

# 最大収益
max_income = 0
# リンゴの最低価格
min_num = A[0]
# 青木君が減らさないといけない組の数
comb = 0
    
# 2つ目の町から探索
# n = 現在の町のリンゴの価格
for n in A[1:]:
    # 最低価格を更新する
    if n < min_num:
        min_num = n
    
    # 最大利益を更新する
    elif n - min_num > max_income:
        max_income = n-min_num
        # 組数を1にする
        comb =1
    
    # 最大利益を持つ組が2個あった場合、
    elif n - min_num == max_income:
        # 組数を1増やす
        comb +=1
        

print(comb)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,T=MI()
    A=LI()
    mini = inf
    mini_cnt = 0
    max_profit = 0
    ans = 0
    for i,a in enumerate(A):
        profit = a-mini
        if max_profit==profit:
            ans += 1
        if max_profit<profit:
            max_profit = profit
            ans = 1
        if mini==a:
            mini_cnt+=1
        if mini>a:
            mini=a
            mini_cnt=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
read = sys.stdin.read

N, T, *A = map(int, read().split())
a_minimum = accumulate(A, min)
a = [i - j for i, j in zip(A, a_minimum)]
minimum = max(a)

print(a.count(minimum))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
read = sys.stdin.read

N, T, *A = map(int, read().split())
a_minimum = list(accumulate(A, min))
a = [i - j for i, j in zip(A, a_minimum)]
minimum = max(a)

print(a.count(minimum))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
read = sys.stdin.read

N, T, *A = map(int, read().split())
a_maximum = list(reversed(list(accumulate(A[::-1], max))[:-1]))
a = [j - i for i, j in zip(A, a_maximum)]
minimum = max(a)

print(a.count(minimum))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
read = sys.stdin.read

N, T, *A = map(int, read().split())
a_maximum = list(list(accumulate(A[::-1], max))[::-1])
a = [j - i for i, j in zip(A, a_maximum[1:])]
minimum = max(a)

print(a.count(minimum))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
read = sys.stdin.read

N, T, *A = map(int, read().split())
a_maximum = list(reversed(list(accumulate(reversed(A), max))))
a = [j - i for i, j in zip(A, a_maximum[1:])]
minimum = max(a)

print(a.count(minimum))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n,t = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
_max = 0
res = []
for a in a_ls[::-1]:
    _max = max(a, _max)
    res.append(_max - a)
ct = Counter(res)
print(ct[max(res)])

Submission status: Accepted

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


def read_list():
    return list(map(int, input().split()))


def main():
    N, T = read_values()
    A = read_list()

    m = A[0]
    p = 0
    D = {}
    for a in A:
        if m > a:
            D[p - m] = D.setdefault(p - m, 0) + 1
            m = a
            p = a
        else:
            p = max(p, a)
    D[p - m] = D.setdefault(p - m, 0) + 1

    k = max(D.keys())
    print(D[k])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
dif = []
max_A = 0
for i in range(N):
    max_A = max(max_A,A[-1-i])
    dif.append(max_A-A[-1-i])
ans = 0
dif.sort(reverse=True)
for i in range(N-1):
    if dif[i]!=dif[i+1]:
        print(i+1)
        break

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a=inf
  b=0
  ans1=[]
  ans2=[]

  N,T=LI()
  l=LI()

  a=l[0]
  for x in l[1:]:
    if x<a:
      ans1.append([a,b])
      ans2.append(b-a)
      a=x
      b=x
    else:
      b=max(b,x)
  ans1.append([a,b])
  ans2.append(b-a)

  ans2.sort()
  return ans2.count(ans2[-1])

# main()
print(main())

Submission status: Accepted

Solution code:
import heapq

N,T = map(int, input().split())
A = [int(a) for a in input().split()]

l = A[0]
l_idx = 0
r = []
for i in range(1, N):
    heapq.heappush(r, (-A[i], i))

b = -r[0][0] - l
h = []
heapq.heappush(h, (-b, l_idx, r[0][1]))
for i in range(1, N-1):
    while r[0][1] <= i:
        heapq.heappop(r)
    if l > A[i]:
        l = A[i]
        l_idx = i
    if b <= -r[0][0]-l:
        b = -r[0][0]-l
        heapq.heappush(h, (-b, l_idx, r[0][1]))
        
used1 = [0]*N
used2 = [0]*N
while h:
    t = heapq.heappop(h)
    if -t[0] < b:
        break
    if used1[t[2]] == 1:
        used1[t[2]] = -1
        used2[t[2]] = -1
    if used2[t[1]] == 1:
        used1[t[1]] = -1
        used2[t[1]] = -1
    if used1[t[1]] == 0:
        used1[t[1]] = 1
    if used2[t[2]] == 0:
        used2[t[2]] = 1
    
cnt1 = 0
cnt2 = 0
for i in range(N):
    cnt1 += max(0, used1[i])
    cnt2 += max(0, used2[i])
    
print(min(cnt1, cnt2))

Submission status: Accepted

Solution code:
# ans = 売る可能性がある場所の数 = 売って利益が最大値になる可能性がある場所
# Tは関係ない

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

# 売る場所を一つず右にずらす
# それより前の場所の最安値を持っておく
# 差分のmaxvalを満たす回数をカウント、maxvalが更新されたら回数は1に戻す

INF=10**9+1
maxval=0
minval=INF
ans=0
for i in range(1,len(A)):
  minval=min(A[i-1],minval)
  diff=A[i]-minval
  if diff>maxval:
    maxval=diff
    ans=1
  elif diff==maxval:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
# 二か所で買ったものを一か所で売ることはあり得ない（安いほうで買いたい）
# 一か所で買ったものを二か所で売ることはあり得ない（高いほうで買いたい）
# 売る場所の数 = 買う場所の数
# ans = 売って最大利益になる場所の数（or 買う場所の数。どっちでもいい）
# Tは関係ない

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

# 売る場所を一つず右にずらす
# それより前の場所の最安値を持っておく
# 差分のmaxvalを満たす回数をカウント、maxvalが更新されたら回数は1に戻す

INF=10**9+1
maxval=0
minval=INF
ans=0
for i in range(1,len(A)):
  minval=min(A[i-1],minval)
  diff=A[i]-minval
  if diff>maxval:
    maxval=diff
    ans=1
  elif diff==maxval:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,t=map(int,input().split())
    A=list(map(int,input().split()))
    S=[None]*n
    S[-1]=A[-1]
    for i in range(n-2,-1,-1):
        S[i]=max(A[i],S[i+1])
    d=max(S[i+1]-A[i] for i in range(n-1))
    print(sum(1 for i in range(n-1) if(S[i+1]-A[i]==d)))
resolve()

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
l=list(map(int,input().split()))
#最大利益を実現する買い方の組がいくつあるか考えたい
#ある地点で売るときはそれより前の地点の一番安いところで買うのが良いーnowminで判断しよう
count=0
max=0
nowmin=l[0]
nowmincount=1
for i in range(1,n):
  if l[i]-nowmin>max:
    max=l[i]-nowmin
    count=nowmincount
  elif l[i]-nowmin==max:
    count+=nowmincount
  elif nowmin>l[i]:
    nowmincount=1
    nowmin=l[i]
  elif nowmin==l[i]:
    nowmincount+=1
print(count)

Submission status: Accepted

Solution code:
def main():
    n,t = map(int,input().split())
    a = [int(x) for x in input().split()]
    a_min = []
    ap = a_min.append
    ap(a[0])
    for i in range(1,n):
        ap(min(a_min[-1],a[i]))
    a_sub = []
    ap = a_sub.append
    for i in range(n):
        ap(a[i]-a_min[i])
    print(a_sub.count(max(a_sub)))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
max=0
min=1000000000000000000000000000000000000
ans=1
for i in range(len(a)-1):
  if a[i]<min:
    min=a[i]
  elif min==a[i] or max==a[i]-min:
    ans+=1
  elif max<a[i]-min:
    ans=1
    max=a[i]-min
if a[len(a)-1]-min==max:
  ans+=1
print(ans)

Submission status: Accepted

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

c=0
dif=0
m=a[0]
for i in range(1,n):
    if(m>a[i]):
        m=a[i]
    if(dif<a[i]-m):
        c=1
        dif=a[i]-m
    elif(dif==a[i]-m):
        c+=1
print(c)

Submission status: Accepted

Solution code:

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

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

nmin = float("inf")
nsub = 0
ans = 0

Acopy = A.copy()
Acopy.sort()

for i in Acopy:

    if A[-1] == i:
        del A[-1]
    else:
        break


for i in range(len(A)):

    nmin = min(nmin , A[i])

    if nsub < A[i] - nmin:
        nsub = A[i] - nmin
        ans = 1

    elif nsub == A[i] - nmin:
        ans += 1

print (ans)

Submission status: Accepted

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

max=N-1
low=0
maxnum=0
dif = -1

for i in range(1,len(A)):
    if(A[low]>A[i]):
        low=i
    else:
        if(A[i] - A[low] > dif):
            dif=A[i] - A[low]
            maxnum=1
        elif(dif==A[i] - A[low]):
            maxnum+=1

print(maxnum)

Submission status: Accepted

Solution code:
n, t = list(map(int, input().split()))
a = list(map(int, input().split()))
dif_list = [0] * n
max_list = [0 for i  in range(n)]
a.reverse()
max_list[0] = a[0]
for i in range(1,n):
    max_list[i] = max(max_list[i-1], a[i])
max_list.reverse()
a.reverse()
for i in range(0,n):
    dif_list[i] = max_list[i] - a[i]

k = max(dif_list)
count = 0
for i in range(n):
    if k == dif_list[i]:
        count += 1
print(count)

Submission status: Accepted

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

r=N-1
p=-1
for l in reversed(range(N)):
  if A[l]>A[r]:
    r=l
  else:
    if A[r]-A[l]==p:
      ans+=1
    elif A[r]-A[l]>p:
      ans=1
      p=A[r]-A[l]
      
print(ans)

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
minA = [[A[0],0]] + [[-1,-1]]*(N-1)
for i in range(1,N):
  if minA[i-1][0] >= A[i]: minA[i] = [A[i],i]
  else: minA[i] = minA[i-1]
  
maxA = [[-1,-1]]*(N-1) + [[A[-1],N-1]]
for i in range(N-2,-1,-1):
  if maxA[i][0] <= A[i]: maxA[i] = [A[i],i]
  else: maxA[i] = maxA[i-1]

max_dif = -float('inf')
max_i = []
cnt = 0
for mina, maxa in zip(minA, maxA):
  if max_dif < maxa[0]-mina[0]:
    max_dif = maxa[0]-mina[0]
    max_i = [cnt]
  elif  max_dif == maxa[0]-mina[0]:
    max_i.append(cnt)
  cnt += 1

print(len(max_i))

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
A = list(map(int,input().split()))
m = 10**9+1 
M = -1
ans = 1
for i in range(n):
    x = A[i]
    m = min(x,m)
    p = x-m
    if p > M:
        ans = 1
        M = p
    elif p == M:
        ans += 1
if M <= 0:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
list1=[0]*n
list1[0]=a[0]
list2=[0]*n
list2[n-1]=a[n-1]
for i in range(1,n):
    list1[i]=min(list1[i-1],a[i])
for i in range(n-2,-1,-1):
    list2[i]=max(list2[i+1],a[i])
lst=[]
for i in range(n):
    lst.append([list2[i]-list1[i],list1[i]])
count=1
lst.sort(reverse=True)
for i in range(1,n):
    if lst[i][0]==lst[i-1][0]:
        if lst[i][1]!=lst[i-1][1]:
            count+=1
    else:
        break
print(count)

Submission status: Accepted

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

mi=[a[0]]
ma=[a[n-1]]
for i in range(1,n):
    if a[i]<mi[-1]:
        mi.append(a[i])
    else:
        mi.append(mi[-1])

for i in range(n-2,-1,-1):
    if a[i]>ma[-1]:
        ma.append(a[i])
    else:
        ma.append(ma[-1])

ma.reverse()

sa=0
for i in range(n):
    x=ma[i]-mi[i]
    sa=max(sa,x)
se=set()
for i in range(n):
    if ma[i]-mi[i]==sa:
        se.add(mi[i])

print(len(se))

Submission status: Accepted

Solution code:
import heapq

def solve():
    N, T = tuple(map(int, input().split()))
    AS = tuple(map(int, input().split()))

    # print(N, T)
    # print(AS)

    lis = []
    D = {}

    m = -float('inf')
    c = 0
    for i in range(len(AS) - 1, -1, -1):
        x = AS[i]
        heapq.heappush(lis, -x)
        D[i] = -lis[0]

    for i in range(len(AS)):
        x = AS[i]

        d = D[i] - AS[i]
        if d > 0:
            if m < d:
                m = d
                c = 1
            elif m == d:  # max と同じ値なら counter を ++
                c += 1

    return c


if __name__ == '__main__':
    res = solve()
    print(res)

Submission status: Accepted

Solution code:
import numpy as np
N,T = map(int,input().split())
A=np.array(input().split(),dtype=np.int32)
s=A-np.minimum.accumulate(A)
print((s==max(s)).sum())

Submission status: Accepted

Solution code:
# python3 (3.4.3)
import sys
input = sys.stdin.readline

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

lowest = 10**9+1
profit = 0
ans = 0

for a in A:
    lowest = min(lowest, a)
    if a - lowest == profit:
        ans += 1
    elif a - lowest > profit:
        profit = a - lowest
        ans = 1

print(ans)

Submission status: Accepted

Solution code:
def examD():
    N, T =LI()
    A = LI()
    maXI = [0]*N
    maXI[N-1] = A[N-1]
    for i in range(1,N):
        maXI[N-i-1] = max(maXI[N-i],A[N-i-1])
    maXAD = int(0)
    for i in range(N-1):
        maXAD = max(maXAD,maXI[i+1]-A[i])
    cur = int(0)
    for i in range(N-1):
        if maXI[i+1]-A[i]==maXAD:
            cur +=1
    print(cur)



import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

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

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

"""
先頭からAを見ていって、最小値を保存しておく。
例えば先頭から何番目かまで見ていって最小値が４の時、それ以降で最大利益が更新される場合、その組の最小値は４以下。
例えば（4,10）とかだった最大利益の組が、（４，１１）とか（３，１０）とかにかわる（Aに重複がないから）。
ので、最小値と最大利益を覚えておいて、最大利益が同じになる組をかぞえる。
最大利益が更新されたら組の数を１にする
最後に組の数を出力
"""
max_income = 0
min_num = A[0]
comb = 0

for n in A[1:]:
    # 最小値が更新される場合
    if n < min_num:
        min_num = n
    #最大利益が更新される場合
    # (4,9)が最大利益の時に10が出てくるとか
    elif n - min_num > max_income:
        max_income = n - min_num
        comb = 1
    #最大利益が同じ組が見つかった場合
    #(4,9)が最大利益のときに、3->8とか出てくるなど。
    #(5以上,x)で最大利益の組がみつかることはない（４との組で最大利益が更新されるから）
    elif n - min_num == max_income:
        comb += 1

print(comb)

Submission status: Accepted

Solution code:
import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]

LL = [[0] for i in range(n)]
tmax = L[-1]
for i in range(n):
  if tmax <= L[-i-1]:
    tmax = L[-i-1]
  LL[-i-1] = tmax
 
minvalue = L[0]
maxvalue = LL[0]
subt = 0
count = 1
flag = 0
flagg = 0
j = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  
  maxvalue = LL[i]
 
  #if maxvalue == L[i]:
    #LL = LL[i-j+1:]
    #maxvalue = max(LL)
    #j = i+1
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
  #print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
B = [(0,-1) for _ in range(N)]
amax = A[-1]
ind = N-1
bmax = 0
for i in range(N-2,-1,-1):
    a = A[i]
    if a>amax:
        amax = a
        ind = i
    else:
        B[i] = (amax-a,ind)
        if bmax<amax-a:
            bmax = amax-a
C = []
for i in range(N):
    if B[i][0]==bmax:
        if B[i][1] not in C:
            C.append(B[i][1])
print(len(C))

Submission status: Accepted

Solution code:
from numpy import*;_,a=open(0);*a,=map(int,a.split());c=array(a)-minimum.accumulate(a);print(sum(c==max(c)))

Submission status: Accepted

Solution code:
from numpy import*;_,a=open(0);*a,=map(int,a.split());c=array(a)-minimum.accumulate(a);print(list(c).count(max(c)))

Submission status: Accepted

Solution code:
from copy import*
from numpy import*
a,b=map(int,input().split())
*c,=map(int,input().split())
c1=deepcopy(c)
c2=deepcopy(c)

for i in range(1,a):
    c1[i]=min(c1[i-1],c1[i])
for i in range(a-1,0,-1):
    c2[i-1]=max(c2[i],c2[i-1])

#print(c1,c2)
d=array(c2)-array(c1)
d2=array(c)-array(c1)
print(list(d2).count(max(d)))

Submission status: Accepted

Solution code:
[n,t]=list(map(int,input().split()))
alist=list(map(int,input().split()))
salist=[alist[1]-alist[0]]
saisho=min(alist[0],alist[1])
for i in range(1,n-1):
	saisho=min(saisho,alist[i])
	salist.append(alist[i+1]-saisho)
saidai=max(salist)
kaisu=salist.count(saidai)
print(kaisu)

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)
    m = 10 ** 10
    for v in a:
        if v < m:
            m = v
        else:
            d[v-m] += [m]
    d = sorted(d.items(), key=lambda x: x[0], reverse=True)
    print(len(d[0][1]))


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
input();A=list(map(int,input().split()));b,B=A[0],[];
for i in range(1,len(A)):
  b=min(b,A[i]);B.append(A[i]-b);
print(B.count(max(B)))

Submission status: Accepted

Solution code:
input()
A=list(map(int,input().split()))
b,B=A[0],[]
for i in range(1,len(A)):
  b=min(b,A[i])
  B.append(A[i]-b)
print(B.count(max(B)))