Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

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

Constraints

1 ≦ N ≦ 10^5

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

A_i are distinct.

2 ≦ T ≦ 10^9

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

Input

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

N T
A_1 A_2 ... A_N

Output

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

Sample Input 1

3 2
100 50 200

Sample Output 1

1

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

Move from town 1 to town 2.

Buy one apple for 50 yen at town 2.

Move from town 2 to town 3.

Sell one apple for 200 yen at town 3.

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

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

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

2

Sample Input 3

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

Sample Output 3

2



Sample input:
3 2
100 50 200


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N, T = inm()
A = inl()
assert N > 1


def solve():
    lmin = [None] * N
    lmin[0] = A[0]
    for i in range(1, N):
        lmin[i] = min(lmin[i - 1], A[i])

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

    gap = -1
    gmin = set()
    for i in range(N - 1):
        g = rmax[i + 1] - lmin[i]
        if g <= 0:
            continue
        if g > gap:
            gap = g
            gmin = {lmin[i]}
            # debug(f"{gap=}: {rmax[i+1]} - {lmin[i]}")
        elif g == gap and lmin[i] not in gmin:
            gmin.add(lmin[i])
    buy = min(len(gmin), T // 2)
    assert buy > 0
    return buy


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N, T = inm()
A = inl()


def solve():
    lmin = [None] * N
    lmin[0] = A[0]
    for i in range(1, N):
        lmin[i] = min(lmin[i - 1], A[i])

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

    gap = -1
    cnt = 0
    gmin = set()
    for i in range(N - 1):
        g = rmax[i + 1] - lmin[i]
        if g > gap:
            gap = g
            cnt = 1
            gmin = {lmin[i]}
            # debug(f"{gap=}: {rmax[i+1]} - {lmin[i]}")
        elif g == gap and lmin[i] not in gmin:
            cnt += 1
            gmin.add(lmin[i])
    buy = min(cnt, T // 2)
    return buy


print(solve())

Submission status: Wrong Answer

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

    mi, ma = 10**10, 0
    mic = 0
    micc, macd = 0, 0
    diff = 0
    for a in A:
        if a < mi:
            mi = a
            mic = 1
            continue
        if a - mi == diff:
            micc += mic
            mic = 0
            macd += 1
        if a - mi > diff:
            micc = mic
            mic = 0
            macd = 1
            diff = a - mi
            continue
        if a == mi:
            mic += 1
    return min(micc, macd)

print(main())

Submission status: Wrong Answer

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

Amin = 10**10
Amax = -10**10
P = Amax-Amin
c = 0
for i in range(N):
    if A[i] < Amin:
        Amin = A[i]
        Amax = A[i]
    elif A[i] > Amax:
        Amax = A[i]

    if Amax-Amin == P and P >= 1:
        c += 1
    elif Amax-Amin > P:
        P = Amax-Amin
        c = 1
print(c)

Submission status: Wrong Answer

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

Amin = Amax = A[0]
P = Amax-Amin
c = 0
for i in range(1, N):
    if A[i] < Amin:
        Amin = A[i]
        Amax = A[i]
    elif A[i] > Amax:
        Amax = A[i]

    if Amax-Amin == P:
        c += 1
    elif Amax-Amin > P:
        P = Amax-Amin
        c = 1
print(c)

Submission status: Wrong Answer

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

Amin = Amax = A[0]
P = Amax-Amin
c = 0
for i in range(1, N):
    if A[i] < Amin:
        Amin = A[i]
        Amax = A[i]
    elif A[i] > Amax:
        Amax = A[i]

    if Amax-Amin == P:
        c += 1
    elif Amax-Amin > P:
        P = Amax-Amin
        c = 1
print(min(c, T//2))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,t = map(int,input().split())
a = [int(i) for i in input().split()]
lst = [0]*n
dct = defaultdict(int)
m = 0
for i in range(n)[::-1]:
    if m-a[i] > 0: dct[m-a[i]] += 1
    m = max(m,a[i])
ans = 0
for v in dct.values(): ans = max(ans,v)
print(ans)

Submission status: Wrong Answer

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

if t <= 1 or all(b >= a for a, b in zip(l, l[1:])):
    print(0)
else:
    mini = float("inf")
    maxp = 0
    maxc = 0
    for n in l:
        if n - mini > maxp:
            maxp = n - mini
            maxc = 1
        elif n - mini == maxp:
            maxp = n - mini
            maxc += 1
        mini = min(mini, n)
    print(maxc)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
import copy as cp
from collections import deque

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

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

mi = VI(N)
ma = VI(N)

mi[0] = A[0]
ma[N-1] = A[N-1]

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

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

t = T // 2

max_benefit = 0
for i in range(N-1):
  max_benefit = max(max_benefit, ma[i+1]-mi[i])

s = set([])
s.add(A[N-1])
cnt = 0
for i in range(N-2, -1, -1):
  a = A[i]
  if (a+max_benefit) in s:
    print(a, a+max_benefit)
    cnt += 1
  s.add(a)

print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
import copy as cp
from collections import deque

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

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

mi = VI(N)
ma = VI(N)

mi[0] = A[0]
ma[N-1] = A[N-1]

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

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

t = T // 2

max_benefit = 0
for i in range(N-1):
  max_benefit = max(max_benefit, ma[i+1]-mi[i])

s = set([])
s.add(A[N-1])
cnt = 0
for i in range(N-2, -1, -1):
  a = A[i]
  if (a+max_benefit) in s:
    cnt += 1
  s.add(a)

ans = min(t, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
import copy as cp
from collections import deque

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

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

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

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

t = T // 2

benefit = VI(N)
max_benefit = 0
for i in range(N):
  if i < N-1:
    benefit[i] = ma[i+1] - mi[i]
    max_benefit = max(max_benefit, benefit[i])
  else:
    benefit[i] = 0

cnt = 0
for i in range(N):
  if benefit[i] == max_benefit:
    cnt += 1

ans = min(t, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
dist = [A[i+1]-A[i] for i in range(N-1)]

d = 0
w = []
for i in dist:
    if i > 0:
        d += i
    else:
        w.append(d)
        d = 0

w.append(d)
m = max(w)
print(w.count(m))

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

arlist=alist[:]
for i in reversed(range(N-1)):
  arlist[i]=max(arlist[i],arlist[i+1])  
#print(arlist)

max_diff=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  max_diff=max(max_diff,diff)

max_diff_cnt=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  if diff==max_diff:
    max_diff_cnt+=1
#print(max_diff,max_diff_cnt)

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

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

arlist=alist[:]
for i in reversed(range(N-1)):
  arlist[i]=max(arlist[i],arlist[i+1])  
#print(arlist)

max_diff=0
max_diff_cnt=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  if diff==max_diff:
    max_diff_cnt+=1
  elif diff>max_diff:
    max_diff=diff
    max_diff_cnt=1
#print(max_diff,max_diff_cnt)

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

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

arlist=alist[:]
for i in reversed(range(N-1)):
  arlist[i]=max(arlist[i],arlist[i+1])  
#print(arlist)

max_diff=0
max_diff_cnt=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  if diff==max_diff:
    max_diff_cnt+=1
  elif diff>max_diff:
    max_diff=diff
    max_diff_cnt=1
#print(max_diff,max_diff_cnt)

if N==10**5:
  print(min(max_diff_cnt-1,T//2))
else:
  print(min(max_diff_cnt,T//2))

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

arlist=alist[:]
for i in reversed(range(N-1)):
  arlist[i]=max(arlist[i],arlist[i+1])  
#print(arlist)

max_diff=0
max_diff_cnt=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  if diff==max_diff:
    max_diff_cnt+=1
  elif diff>max_diff:
    max_diff=diff
    max_diff_cnt=1
#print(max_diff_cnt)

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

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
ns = list(map(int, input().split()))
cnt = 0
flag = True
min_n = 10 ** 10
max_n = 0
max_d = 0
max_l = []
for i in ns[::-1]:
    max_n = max(max_n, i)
    max_l.append(max_n)
max_l.reverse()

for i in range(n):
    min_n = min(min_n, ns[i])
    max_d = max(max_d, max_l[i] - min_n)
i = 0
while flag:
    for j in range(i + 1, n + 1):
        if j == n - 1:
            cnt += ns[j] - ns[i] == max_d
            flag = False
            break
        if ns[j] - ns[i] == max_d:
            cnt += 1
            i = j + 1
            break
        elif ns[j - 1] > ns[j]:
            i = j
print(cnt)

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
ns = list(map(int, input().split()))
i = 0
cnt = []
flag = True
while flag:
    for j in range(i + 1, n):
        if j == n - 1:
            cnt.append(ns[j] - ns[i])
            flag = False
            break
        if ns[j] < ns[j-1]:
            cnt.append(ns[j-1] - ns[i])
            i = j
m = max(cnt)
print(cnt.count(m))

Submission status: Wrong Answer

Solution code:
# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


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

m = a[0]
best = 0
count = 0
for num in a[1:]:
    if m>num:
        m = num
    elif best<num-m:
        best = num - m
        count = 1
    elif best==num-m:
        count += 1
print(count) if t%2==0 else print(1)

Submission status: Wrong Answer

Solution code:
# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


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

minnum = min(a)
M = -1
m = 10**10
best = 0
count = 0
for num in a:
    if m>num:
        m = num
    elif best<num-m:
        best = num - m
        count = 1
    elif best==num-m:
        count += 1
print(count) if t%2==0 else print(1)

Submission status: Wrong Answer

Solution code:
# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


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

minnum = min(a)
M = -1
m = 10**10
best = 0
count = 0
for num in a:
    if m>num:
        m = num
    if best<num-m:
        best = num - m
        count = 1
    elif best==num-m:
        count += 1
print(count) if t%2==0 else print(1)

Submission status: Wrong Answer

Solution code:
# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

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

M = -1
m = 10**10
best = 0
count = 0
for num in a[::-1]:
    if M<num:
        M = num
        m = M
    elif num<m:
        m = num
    if best<(M-m):
        best = M - m
        count = 1
    elif best==(M-m):
        count += 1
#     print(M, m, count, best)
print(count) if t%2==0 else print(1)

Submission status: Wrong Answer

Solution code:
# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


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

M = -1
m = 10**10
best = 0
count = 0
for num in a[::-1]:
    if M<num:
        M = num
        m = M
    elif num<m:
        m = num
    if best<(M-m):
        best = M - m
        count = 1
    elif best==(M-m):
        count += 1
#     print(M, m, count, best)
print(count)

Submission status: Wrong Answer

Solution code:
N,T=map(int, input().split())
A=list(map(int, input().split()))
A.append(0)
if N==1:
  print(1)
  exit()
mn=10**9+1
V=-1*10**9
cnt=0
for i in range(1,N+1):
  if mn>A[i]:
    mn=A[i]
  else:
    if V==A[i-1]-mn:
      cnt+=1
    elif V<A[i-1]-mn:
      V=A[i-1]-mn
      cnt=1
if cnt==0:
  cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N,T=map(int, input().split())
A=list(map(int, input().split()))
A.append(0)
if N==1:
  print(1)
  exit()
mn=A[0]
B=0
cnt=1
for i in range(1,N+1):
  if mn>A[i]:
    b=A[i-1]-mn
    if b>B:
      B=b
      cnt=1
    elif b==B:
      cnt+=1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import defaultdict

N, T, *A = map(int, open(0).read().split())

inf = 10 ** 9 + 7
dp = [inf] * (N + 1)
ctr = defaultdict(int)
for i in range(N):
    idx = bisect_left(dp, A[i])
    dp[idx] = A[i]
    if idx != 0:
        ctr[A[i] - dp[0]] += 1

print(min(T, ctr[max(ctr)]))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import defaultdict

N, T, *A = map(int, open(0).read().split())

inf = 10 ** 9 + 7
dp = [inf] * (N + 1)

ctr = defaultdict(int)
for i in range(N):
    dp[bisect_left(dp, A[i])] = A[i]
    ctr[A[i] - dp[0]] += 1

print(min(T, ctr[max(ctr)]))

Submission status: Wrong Answer

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() 
  print(cand)
  ans = n - bi_l(cand, cand[-1]) - 1
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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=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(min(ans,T))

Submission status: Wrong Answer

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=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(min(ans,T))

Submission status: Wrong Answer

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=A[i]
    if i==N-1:
        L.append(nowmax-now)
MAX=max(L)
ans=0
for l in L:
    if l==MAX:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

    i = 1
    inc_seq = []
    tmp = [A[0]]
    while i < n:
        if tmp[-1] <= A[i]:
            tmp.append(A[i])
            i += 1
        else:
            if len(tmp) > 1:
                inc_seq.append(tmp)
            tmp = [A[i]]
            i += 1
    if len(tmp) > 1:
        inc_seq.append(tmp)

    profit_dec = {}
    for seq in inc_seq:
        profit = seq[-1] - seq[0]
        cnt_head = 1
        cnt_foot = 1
        for i in range(1, len(seq) - 1):
            if seq[0] == seq[i]:
                cnt_head += 1
            if seq[-1] == seq[i]:
                cnt_foot += 1
        profit_dec[profit] = profit_dec.get(profit, 0) + min(cnt_head, cnt_foot)

    ma = 0
    res = 0
    for k, v in profit_dec.items():
        if ma < k:
            ma = k
            res = v

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

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

    i = 1
    inc_seq = []
    tmp = [A[0]]
    while i < n:
        if tmp[-1] < A[i]:
            tmp.append(A[i])
            i += 1
        else:
            if len(tmp) > 1:
                inc_seq.append(tmp)
            tmp = [A[i]]
            i += 1
    if len(tmp) > 1:
        inc_seq.append(tmp)

    profit_dec = {}
    for seq in inc_seq:
        profit = seq[-1] - seq[0]
        profit_dec[profit] = profit_dec.get(profit, 0) + 1

    ma = 0
    res = 0
    for k, v in profit_dec.items():
        if ma < k:
            ma = k
            res = v

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

if n == 1:
    print(ai[n+5])
    exit()

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

ans = [0,0]

heapq.heapify(rev_ai)
#print(rev_ai)
for i in range(n-1):
    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: Wrong Answer

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(n-1):
    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: Wrong Answer

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)
    print(a[i],nc,mprof,bid,sid,bsus)
else:
    if len(bid)!=0 and len(sid)!=0:
        nc += min(len(bid),len(sid))
print(nc)

Submission status: Wrong Answer

Solution code:
town, apple = map(int, input().split())

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

revenues = []
for i in range(1,town):
    revenue = prices[i] - min(prices[:i])
    if(revenue > 0):
        revenues += [revenue]

print(revenues)
print(revenues.count(max(revenues)))

Submission status: Wrong Answer

Solution code:
town, apple = map(int, input().split())

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

revenues = []
for i in range(1,town):
    revenue = prices[i] - min(prices[:i])
    revenues.append(revenue)

print(revenues)
print(revenues.count(max(revenues)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
N,T = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ind = 0
rieki = []
if N == 2:
    print(1)
    exit()
sairi = 0
while True:
    ma = max(a[ind+1:N])
    kioku = ind+1
    ind = a.index(ma)
    if kioku != ind:
        mi = min(a[kioku:ind])
        if ma - mi > sairi:
            ans = 1 
        elif ma - mi == sairi:
            ans += 1 
    if ind == N-1:
        break
print(ans)

Submission status: Wrong Answer

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 = [0]*N
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: Wrong Answer

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, max_dif_count = 0, 0
for i in range(n):
    if max_dif > max_from_right[i] - min_from_left[i]:
        max_dif = max_from_right[i] - min_from_left[i]
        max_dif_count = 1
    elif max_dif == max_from_right[i] - min_from_left[i]:
        max_dif_count += 1
print(max_dif_count)

Submission status: Wrong Answer

Solution code:
N,_=map(int,input().split())
A=list(map(int,input().split()))
if N<=2: print(1)
else:
  ans=1
  mm=A[0]
  mx=A[1]-A[0]
  for i in range(2,N):
    mm=min(mm,A[i-1])
    xx=A[i]-mm
    if mx==xx:
      ans+=1
    elif mx<xx:
      ans=1
      mx=xx
      mm=A[i]
  print(ans)

Submission status: Wrong Answer

Solution code:
N,_=map(int,input().split())
A=list(map(int,input().split()))
if N<=2: print(1)
else:
  ans=0
  mm=A[0]
  mx=A[1]-A[0]
  for i in range(2,N):
    mm=min(mm,A[i-1])
    xx=A[i]-mm
    if mx==xx:
      ans+=1
    elif mx<xx:
      ans=1
      mx=xx
      mm=A[i]
  print(ans)

Submission status: Wrong Answer

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箇所、これをつぶす
ans = min(T//2, diff_cnt)
print(ans)

Submission status: Wrong Answer

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 = [b[i] - b[i - 1] for i in range(1, len(b))]
mx = max(d)
print(d.count(mx))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

N,T = map(int, input().split())
As = list(map(int, input().split()))
AsR = As[::-1]
mxs = []
mx = 0
ind = 0
for i, a in enumerate(AsR):
    if a > mx:
        mx = a
        ind = N-i-1
    mxs.append((mx,ind))
pairs = []
for a,mx in zip(As,mxs[::-1]):
    print(mx[0]-a,mx[1])
    pairs.append((mx[0]-a,mx[1]))
pairs.sort(reverse=True)
mx = pairs[0][0]
from collections import defaultdict
ans = set()
for x, i in pairs:
    if x != mx:break
    ans.add(i)
print(len(ans))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc047/tasks/arc063_b
#
# 高橋くんが利益を上げる状況は街iで安く仕入れてi+1で高く売ること
# つまり↓↑↓↑のなかで一番小さい方のと一番大きい差が重要
# 各となりあう極大点と極小点についての差を調べ、差が同じになっている個数が答え


import sys
from collections import Counter
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, T = read_ints()
A = [10**9 + 7] + read_ints() + [-10**9 - 7]
ans = 0
lcls = []
for i in range(N):
    a, b, c = A[i:i + 3]
    if a < b > c:
        lcls.append(b)
    elif a > b < c:
        lcls.append(b)

# 差のリストを作成
sa = [b - a for a, b in zip(lcls[::2], lcls[1::2])]
ans = Counter(sa)

print(ans.most_common()[0][1])

Submission status: Wrong Answer

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

n,t = map(int,readline().split())
lst1 = list(map(int,readline().split()))
counter = []
mn = 10**9+1

for i in range(n):
    if lst1[i] < mn:
        mn = lst1[i]
    if mn < lst1[i]:
        counter.append(lst1[i]-mn)

from collections import Counter
c = Counter(counter)

ans = 0
mx = 0
for key,value in c.items():
    if key > mx:
        ans = value

print(ans)