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:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    A = list(map(int, input().split()))

    MAX_S = []
    max_s = 0
    for a in A[::-1]:
        if max_s < a:
            max_s = a
        MAX_S.append(max_s)
    MAX_S = MAX_S[::-1]

    cnt = defaultdict(int)
    for a, s in zip(A, MAX_S):
        cnt[s - a] += 1

    res = sorted(cnt.items(), reverse=True)
    print(res[0][1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N,T=map(int, input().split())
A=list(map(int, input().split()))
L=[]
for i in range(N):
    if i==0:
        now=A[i]
        nowmax=now
    if now>A[i]:
        L.append(nowmax-now)
        now=A[i]
        nowmax=now
    else:
        nowmax=max(nowmax,A[i])
    if i==N-1:
        L.append(nowmax-now)
MAX=max(L)
ans=0
#print(L)
for l in L:
    if l==MAX:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, _ = map(int, input().split())
A = list(map(int, input().split()))

MAX_S = []
max_s = 0
for a in A[::-1]:
    if max_s < a:
        max_s = a
    MAX_S.append(max_s)
MAX_S = MAX_S[::-1]
cnt = defaultdict(int)
for a, s in zip(A, MAX_S):
    cnt[s-a] += 1

print(sorted(cnt.items(), reverse=True)[0][1])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bi_l

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

def main():
  cand = []
  mi = a[0]
  for x in a[1:]:
    cand.append(x - mi)
    mi = min(mi, x)
  cand.sort() 
  ans = n - bi_l(cand, cand[-1]) - 1
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    N, T = map(int, input().split())
    *A, = map(int, input().split())

    mi = A[0]
    d_ma = -1
    cnt = 0
    for x in A:
        d = x - mi
        if d_ma < d:
            d_ma = d
            cnt = 1
        elif d_ma == d:
            cnt += 1
        if mi > x:
            mi = x

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

def main():
  cand = []
  mi = a[0]
  for x in a[1:]:
    cand.append(x - mi)
    mi = min(mi, x)
  c = Counter(cand)
  ans = c[max(c.keys())]
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from collections import Counter

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

def main():
  cand = []
  hq = [a[0]]
  for x in a[1:]:
    y = heappop(hq)
    cand.append(x - y)
    heappush(hq, x)
    heappush(hq, y)
  c = Counter(cand)
  ans = c[max(c.keys())]
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush

    inf = 1 << 30

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

    h = [inf]
    ma = -1
    cnt = 0
    for x in A:
        d = x - h[0]
        if ma < d:
            ma = d
            cnt = 1
        elif ma == d:
            cnt += 1
        heappush(h, x)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,t = map(int,input().split())
    a = list(map(int,input().split()))
    b = [0]*n
    ma = a[0]
    mi = a[0]

    for i in range(1,n):
        if a[i] > ma:
            ma = a[i]
            b[i] = ma-mi
        if a[i] < mi:
            ma = a[i]
            mi = a[i]
    print(b.count(max(b)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
a = list(map(int,input().split()))
mdic = {}
mx = 0
import heapq
h = []
heapq.heappush(h,a[0])

for i in range(1,n):
    if mx == a[i]-h[0]:
        mdic[mx] += 1
    if mx < a[i]-h[0]:
        mx = a[i]-h[0]
        mdic[mx] = 1
    heapq.heappush(h,a[i])
#print(h[0])
mlist = sorted(list(mdic.items()))
#print(mlist)
print(mlist[-1][1])

Submission status: Accepted

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

mi = 10**18
mx = -10**18
ans = 0
for a in A:
    if mx < a - mi:
        ans = 0
        mx = a - mi
    if mx == a - mi:
        ans += 1
    mi = min(mi, a)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
C = {}
amin = A[0]
for i in range(1,N):
    a = A[i]
    if a>amin:
        b = a-amin
        if b not in C:
            C[b] = []
        C[b].append(i)
    elif a==amin:
        continue
    else:
        amin = a
C = sorted(list(C.items()),key=lambda x:x[0],reverse=True)
print(len(C[0][1]))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = False

n, t = MAP()
a = LIST()
b = [0 for _ in range(n)]
b[0] = a[0]
for i in range(1, n):
    if b[i - 1] > a[i]:
        b[i] = a[i]
    else:
        b[i] = b[i - 1]
debug(b)
c = [0 for _ in range(n)]
for i in range(n):
    c[i] = a[i] - b[i]
debug(c)
print(c.count(max(c)))

Submission status: Accepted

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

mx = [0] * (N + 1)
for i, a in enumerate(A[::-1], start=1):
    mx[-i] = max(mx[-i + 1], a)

mxD = 0
ans = 0
for i, a in enumerate(A):
    d = mx[i + 1] - a
    if mxD < d:
        mxD = d
        ans = 0
    if mxD == d:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, t = map(int, input().split())
A = list(map(int, input().split()))

MAX_S = []
max_tmp = 0
for a in A[::-1]:
    if max_tmp < a:
        max_tmp = a
    MAX_S.append(max_tmp)
MAX_S = MAX_S[::-1]
cnt = defaultdict(int)
for a, s in zip(A, MAX_S):
    cnt[s-a] += 1

c = [(k, v) for k, v in cnt.items()]
c.sort(reverse=True)
print(c[0][-1])

Submission status: Accepted

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

limit = 0
tmp = A[0]
for a in A[1:]:
   limit = max(limit, a - tmp)
   tmp = min(tmp, a)

ans = [0] * N
maximum = A[-1]
ans[-1] = maximum
for i in range(N - 2, -1, -1):
    ans[i] = maximum - limit #これより安くする必要がある
    maximum = max(maximum, A[i])

tmp = 0
for i in range(N - 1):
    tmp += max(0, ans[i] - A[i] + 1)

# print (A)
# print (ans)
print (tmp)

Submission status: Accepted

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


#rev_ai = [ai[n-1]*(-1)]

ans = [0,0]

max_ai = ai[n-1]

#heapq.heapify(rev_ai)
#print(rev_ai)
for i in range(1,n):
    #print(ai[n-1-i])
    dif = max_ai - ai[n-1-i]
    if dif > ans[0]:
        ans = [dif,1]
    elif dif == ans[0]:
        ans[1] += 1
    #print(rev_ai[0])
    #heapq.heappush(rev_ai,ai[n-1-i]*(-1))
    max_ai = max(max_ai,ai[n-1-i])

print(ans[1])

Submission status: Accepted

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


rev_ai = [ai[n-1]*(-1)]

ans = [0,0]

heapq.heapify(rev_ai)
#print(rev_ai)
for i in range(1,n):
    #print(ai[n-1-i])
    dif = rev_ai[0]*(-1) - ai[n-1-i]
    if dif > ans[0]:
        ans = [dif,1]
    elif dif == ans[0]:
        ans[1] += 1
    #print(rev_ai[0])
    heapq.heappush(rev_ai,ai[n-1-i]*(-1))

print(ans[1])

Submission status: Accepted

Solution code:
n,t= map(int,input().split())
a= list(map(int,input().split()))
mp,mprof = 999999999,0
bid = []
bsus = []
sid = []
nc=0
for i in range(n):
    cp = a[i]-mp
    if cp<0:
        nc += min(len(bid),len(sid))
        mp = a[i]
        sid=[]
        bid=[]
        bsus=[i]
    elif cp>0:
        if mprof <= cp:
            bid += bsus
            bsus = []
            if mprof < cp:
                mprof,sid,nc = cp,[i],0
            else:sid.append(i)
    else:bsus.append(i)
else:
    if len(bid)!=0 and len(sid)!=0:
        nc += min(len(bid),len(sid))
print(nc)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,t = na()
a = na()
b = [0]
c = a[0]
for i in range(1,n):
    b.append(a[i]-c)
    c = min(c,a[i])

print(b.count(max(b)))

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
A = list(map(int,input().split()))
inf = float('inf')
m = [0]*n
m[0] = A[0]
M = [0]*n
M[n-1] = A[n-1]
for i in range(n-1):
    m[i+1] = min(m[i],A[i+1])
    M[n-i-2] = max(M[n-i-1],A[n-2-i])

delta = [M[i+1] - m[i] for i in range(n-1)]
can = max(delta)
ans = 0
for i,a in enumerate(A):
    if a == m[i] + can:
        ans += 1
print(ans)

Submission status: Accepted

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

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

lowest = float('INF')

gain = 0

repeat = 0

for al in alist:
    if al < lowest:
        lowest = al
        continue
    else:
        if al - lowest == gain:
            repeat += 1
            continue
        if al - lowest > gain:
            gain = al - lowest
            repeat = 0
            continue

print(repeat + 1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,t = map(int, input().split())
    a = list(map(int, input().split()))
    b = [0]*n
    b[-1] = a[-1]
    for i in range(n-2, 0, -1):
        if b[i+1] < a[i]:
            b[i] = a[i]
        else:
            b[i] = b[i+1]
    res = 0
    temp = 0
    for i in range(n-1):
        if temp < b[i+1]-a[i]:
            temp = b[i+1]-a[i]
            res = 1
        elif temp == b[i+1]-a[i]:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][0]:０からiまでの区間に置けるMIN
# dp[i][1]:その区間での左から右への差の最大値
# dp[i][2]:最大値をとるものがいくつあるか
dp=[[float('inf'),0,0] for i in range(n)]

for i in range(n):
    if i==0:
        dp[i][0]=a[i]
    else:
        dp[i][0]=min(dp[i-1][0],a[i])
        if dp[i-1][1]<a[i]-dp[i-1][0]:
            dp[i][1]=a[i]-dp[i-1][0]
            dp[i][2]=1
        elif dp[i-1][1]==a[i]-dp[i-1][0]:
            dp[i][1]=dp[i-1][1]
            dp[i][2]=dp[i-1][2]+1
        else:
            dp[i][1]=dp[i-1][1]
            dp[i][2]=dp[i-1][2]


print(dp[-1][2])

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    N, T = map(int, input().split())
    A = list(map(int, readline().split()))

    L = float('inf')
    cnt = 0
    profit = 0
    for a in A:
        if a - L > profit:
            cnt = 1
            profit = a - L
        elif a - L == profit:
            cnt += 1
        
        if a < L:
            L = a
    
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    N, T = map(int, input().split())
    A = list(map(int, readline().split()))

    if N == 2:
        print(1)
        return
    
    L = SegmentTree(A, min, float('inf'))
    R = SegmentTree(A, max, 0)

    profit = 0
    for i in range(1, N + 1):
        l = L.get(0, i + 1)
        r = R.get(i, N + 1)
        profit = max(profit, r - l)
    
    cnt = 0
    for i in range(N):
        l = L.get(0, i + 1)
        r = R.get(i, N + 1)
        if r - l == profit:
            if l == A[i]:
                L.update(i, l - 1)
            else:
                R.update(i, r + 1)
            cnt += 1
    
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# solution
import io

nim,mike = map(int,input().split())
array = list(map(int,input().split()))
arrays = []
min_a = float("inf")
for a in array:
   min_a = min(a, min_a)
   arrays.append(min_a)
array2 = []
for a,b in zip(array, arrays):
   array2.append(a-b)
array2 = sorted(array2)
print(array2.count(array2[-1]))

Submission status: Accepted

Solution code:
N,T = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ans = []
mi = 10**9
for i in range(N):
    mi = min(mi,a[i])
    ans.append(a[i]-mi)
print(ans.count(max(ans)))

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools
#from scipy.misc import comb

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

Amin = [A[0]] + [0]*(N-1)
for i in range(1,N):
    if A[i] < Amin[i-1]: Amin[i] = A[i]
    else: Amin[i] = Amin[i-1]

B = A[0] - Amin[0]
for i in range(1,N): B = max(B, A[i]-Amin[i])

ans = 0
for i in range(N):
    if A[i] - Amin[i] == B:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans

n, t = map(int, input().split())
a = list(map(int, input().split()))
tree = make_tree(n)
l = len(tree)
for i in range(n):
    update(i, a[i])
b = [0] * n
for i in range(n - 1):
    b[i] = find(i + 1, n - 1) - a[i]
print(b.count(max(b)))

Submission status: Accepted

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

B = []
Amin = A[0]

for i in range(1, N):
  if A[i] < Amin:
    Amin = A[i]
  else:
    B.append(A[i] - Amin)

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

Submission status: Accepted

Solution code:
n,t = map(int, input().split())
a = list(map(int, input().split()))
MAX = []
now = 0
for i in a[::-1]:
  now = max(i,now)
  MAX.append(now)
MAX.reverse()
max_margin = 0
ans = 0
for i,j in zip(a[:-1],MAX[1:]):
  margin = j-i
  if margin > max_margin:
    ans = 1
    max_margin = margin
  elif margin == max_margin:
    ans += 1
print(ans)

Submission status: Accepted

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

result = {}
m = 0
checker = []
for i in range(1, n):
    if m<a[-i]:
        m = a[-i]
    checker.append(m)
checker = checker[::-1]
for i in range(n-1):
    s = checker[i]-a[i]
    if s in result:
        result[s] += 1
    else:
        result[s] = 1
x = max(result.items())
print(x[1])

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
pro = {} #利益がkey売るポイントが何個あるかがvalue
m = A[0]
for i in range(1,N):
    if m > A[i]:
        m = A[i]
    elif A[i]-m not in pro:
        pro[A[i]-m] = 1
    else:
        pro[A[i]-m] += 1

mk = 0
ans = 0
for k, v in pro.items():
    if k > mk:
        mk = k
        ans = v
#print(pro)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,t=map(int,input().split())
a=list(map(int,input().split()))
min_v=a[0]
div=0
for i in range(1,n):
  min_v=min(min_v,a[i])
  div=max(div,a[i]-min_v)
d=defaultdict(int)
for i in range(n):
  d[a[i]]=i
ans=0
for i in range(n):
  if d[a[i]]<d[a[i]+div]:
    ans+=1
print(ans)

Submission status: Accepted

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

ans = defaultdict(int)
min_v = [10**9+1, 1]

for v in a:
    ans[v - min_v[0]] += min_v[1]
    if v < min_v[0]:
        min_v = [v, 1]
    elif v == min_v[0]:
        min_v[1] += 1
ans= sorted(ans.items(), key=lambda x:x[0], reverse=True)
print(ans[0][1])

Submission status: Accepted

Solution code:
# 自分をiとしたとき自分よりあとのjと比べj-iが最大になる箇所の数を数える、という感じ
# （Tは不要？） b
# A[i]はユニークなので
# 左から最小、右から最大を保存?（なんでこれが浮かんだ？）
#       7 10 4 5 9 3 6 8 2 1
# 最小:  7 7 4 4 4 3 3 3 2 1
# 最大: 10 10 9 9 9 8 8 8 2 1
# dif maxの数になる
# だるそうなので集合でやる（ユニークなので）
n, t = map(int, input().split())
arr = list(map(int, input().split()))
min_from_left, max_from_right = [arr[0]], [arr[-1]]
for i in range(1, n):
    min_from_left.append(min(min_from_left[i - 1], arr[i]))
    max_from_right.append(max(max_from_right[i - 1], arr[n - 1 - i]))

max_from_right = max_from_right[::-1]
max_dif = 0
difs = set()
for i in range(n - 1):
    if max_dif < max_from_right[i + 1] - min_from_left[i]:
        max_dif = max_from_right[i + 1] - min_from_left[i]
        difs = set()
        difs.add((max_from_right[i + 1], min_from_left[i]))
    elif max_dif == max_from_right[i + 1] - min_from_left[i]:
        difs.add((max_from_right[i + 1], min_from_left[i]))
print(len(difs))

Submission status: Accepted

Solution code:
import heapq
n,t = map(int,input().split())
a_list = list(map(int,input().split()))
low = a_list[0]
sa = []
for i in range(1,n):
  if a_list[i]>=a_list[i - 1]:
    sa.append(a_list[i] - low)
  elif a_list[i]<= low:
    low = a_list[i]
print(sa.count(max(sa)))

Submission status: Accepted

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

# i番目の町以降の取引金額の最大値
# 末尾はダミー
righter_max = [0] * (N+1)
for i, a in enumerate(A[::-1], 2):
  righter_max[-i] = righter_max[-i+1]
  if righter_max[-i] < a:
    righter_max[-i] = a

ans = 0
max_profit = 0
for i, a in enumerate(A, 1):
  profit = righter_max[i] - a
  if profit == max_profit:
    ans += 1
  elif profit > max_profit:
    max_profit = profit
    ans = 1

print(ans)

Submission status: Accepted

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

min_dif = 0
count = 0
min_val = A[0]

for i in range(1, n):
    if A[i]-min_val > min_dif:
        min_dif = A[i]-min_val
        count = 1
    elif A[i]-min_val == min_dif:
        count += 1

    min_val = min(min_val, A[i])

print(count)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = list(map(lambda x: int(x), input().split()))
#a = list(map(lambda x: int(x), in1.split()))
b = []
strlow = a[0]

for idx1 in range(1, len(a)):
    b.append(a[idx1] - strlow)
    if a[idx1] < strlow:
        strlow = a[idx1]

print(b.count(max(b)))

Submission status: Accepted

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

min_town_price = A[0]
max_profit = -1
max_profit_pairs = 0
for i in range(1, N):
    profit = A[i] - min_town_price
    if max_profit < profit:
        max_profit = profit
        max_profit_pairs = 1
    elif max_profit == profit:
        max_profit_pairs += 1
    min_town_price = min(min_town_price, A[i])
print(max_profit_pairs)

Submission status: Accepted

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

# 買う数 == 売る数
if T % 2 == 1:
    T -= 1

from heapq import heappop,heappush

place = []
MINA = [float("inf")] * N
for i in range(N):
    if i == 0:
        MINA[i] = A[i]
    else:
        MINA[i] = min(MINA[i-1], A[i])

sub = []
for a,m in zip(A,MINA):
    heappush(sub, m - a)

ans = 1
MAXSUB = heappop(sub)
while sub:
    s = heappop(sub)
    if s == MAXSUB:
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

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

pre = 10 ** 18
diff_max = 0
diff_cnt = 0

for a in A:
    if a < pre:
        pre = a
        continue

    if a - pre > diff_max:
        diff_max = a - pre
        diff_cnt = 1
    elif a - pre == diff_max:
        diff_cnt += 1

# 高橋君はdiffmax*(T//2)の利益
# 取引できるのがdiffcnt箇所、これをつぶす
print(diff_cnt)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,T=map(int, input().split())
    *A,=map(int, input().split())
    R=[]
    mn=(A[0],set([0]))
    for i in range(1,N):
        if A[i] > mn[0]:
            R.append((A[i] - mn[0], mn[1]))
        elif mn[0] == A[i]:
            mn[1].add(i)
        else:
            mn = (A[i],set([i]))
    R.sort(reverse=True, key=lambda x:x[0])
    ans = 0
    mx = R[0][0]
    tmp1 = set()
    cnt = 0
    for r in R:
        if r[0] != mx: break
        cnt += 1
        tmp1 |= r[1]
    print(min(cnt, len(tmp1)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, t = MAP()
a = LIST()
get = 0
ans = 0
b = [a[0]]
for i in range(1, n - 1):
    if a[i - 1] < a[i] < a[i + 1]:
        continue
    b.append(a[i])
b.append(a[-1])
d = [0 for i in range(len(b) - 1)]
mn = inf
for i in range(len(b) - 1):
    if mn > b[i]:
        mn = b[i]
    d[i] = b[i + 1] - mn
mx = max(d)
print(d.count(mx))

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
s=list(map(int,input().split()))
mi=s[0]
ma=[]
for i in range(n):
    if s[i]<mi:
        mi=s[i]
    ma.append(s[i]-mi)
ma.sort()
print(ma.count(ma[-1]))

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
mn = A[0]
gain = 0
ans = 1
for a in A[1:]:
    if a < mn:
        mn = a
        continue
    if a-mn == gain:
        ans += 1
    elif a-mn > gain:
        gain = a-mn
        ans = 1
print(ans)

Submission status: Accepted

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

mi = 10**18
miCnt = 1
S = []
for i, a in enumerate(A):
    S.append((a - mi, i, miCnt))
    if a == mi:
        miCnt += 1
    mi = min(mi, a)

S.sort(reverse=True)
S = [c for v, i, c in S if v == S[0][0]]
ans = min(len(S), sum(S))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

m=A[N-1]
maxlist=[A[N-1]]
for i in range(1,N):
    a=A[-i-1]
    m=max(m,a)
    maxlist.append(m)

maxlist=maxlist[::-1]

benefit=defaultdict(int)

for i in range(0,N-1):
    b=-A[i]*(T//2)+maxlist[i+1]*(T//2)
    benefit[b]+=1

ans=0
for key in benefit.keys():
    if benefit[key]>0 and key>ans:
        ans=key

print(benefit[ans])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

B = defaultdict(int)
am = A[0]
for i in range(1, N):
    B[A[i] - am] += 1
    am = min(am, A[i])

print(B[max(B)])

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
*a, = map(int, input().split())
purchase = a[0]
profit = []
for i in range(len(a)):
  profit.append(a[i] - purchase)
  if a[i] < purchase:
    purchase = a[i]
profit.sort()
Answer = profit.count(profit[-1])
print(Answer)

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
A = list(map(int,input().split()))
A_rev = A[::-1]
tmp_max = []
for i, a in enumerate(A_rev):
    if i==0:
        tmp_max = [A_rev[i]]
    else:
        tmp_max += [max(A_rev[i], tmp_max[-1])]
buy = [max(0, x-y) for x,y in zip(tmp_max[::-1], A)]
x = max(buy)
cnt = 0
for b in buy:
    if b==x:
        cnt += 1
print(cnt)

Submission status: Accepted

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

data = [0]*(N-1)
M = [0]*N
M[N-1] = A[N-1]
M_index = [N-1]*N

for i in range(2,N+1):
    if A[N-i] > M[N-i+1]:
        M[N-i] = A[N-i]
        M_index[N-i] = N-i
    else:
        M[N-i] = M[N-i+1]
        M_index[N-i] = M_index[N-i+1]
    data[N-i] = M[N-i] - A[N-i]

m = max(data)
l = []
for i in range(N-1):
    if data[i] == m:
        l.append(i)

ans = [0]*N
for x in l:
    ans[M_index[x]] = 1

#####
#print("A",A)
#print("M",M)
#print("M_index",M_index)
#print("data",data)
#print("ans",ans)
#####

print(sum(ans))