TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
N,T=map(int,input().split())
t=list(map(int,input().split()))

for i in range(0,len(t)-1):
        ans+=min(t[i+1]-t[i],T)
ans+=T
print(ans)

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

ans=0
for i in range(0,len(t)-1):
        ans+=min(t[i+1]-t[i],T)
ans+=T
print(ans)

Verdicts: Runtime Error

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
N,T=map(int,input().split())
a=list(input().split())
ts=[]
for _ in range (len(a)):
    ts.append(int(a[_]))

YU=T

for i in range(1,N):
    if ts[i]-ts[i-1]<T:
        YU+=T-ts[i]-ts[i-1]
    else:
        YU+=T
print (YU)

N,T=map(int,input().split())
a=list(input().split())
ts=[]
for _ in range (len(a)):
    ts.append(int(a[_]))

YU=T

for i in range(1,N):
    if ts[i]-ts[i-1]<T:
        YU+=T-(T-(ts[i]-ts[i-1]))
    else:
        YU+=T
print (YU)

Verdicts: Wrong Answer

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
N, T = map(int,input().split())
t = list(map(int,input().split()))
t.append(T)

ans = 0
for n in range(N):
  ans += min(t[n+1]-t[n],T)
print(ans)

N, T = map(int,input().split())
t = list(map(int,input().split()))
t.append(t[-1]+T)


ans = 0
for n in range(N):
  ans = ans + min(t[n+1]-t[n],T)
  
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
N,T=map(int,input().split(' '))
times=[int(input()) for i in range(N)]
print(sum([min(T, times[i+1]-times[i] for i in range(N-1))])+times[-1])

N,T=map(int,input().split(' '))
times=list(map(int,input().split(' ')))
print(sum([min(T, times[i+1]-times[i]) for i in range(N-1)])+T)


Verdicts: Runtime Error

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
n,T = map(int,input().split())
t = list(map(int,input().split())
A = [0]*n

for i in range(n):
    if t[i]>T:
        A[i+1] = A[i] + T
    else:
        A[i+1] = A[i]+ t[i]
print(A[n])

N, T =map(int, input().split())
t = list(map(int, input().split()))
ans = T
for i in range(1, N):
    if t[i] - t[i-1] >= T:
        ans += T
    else:
        ans += t[i] - t[i-1]
print(ans)

Verdicts: Runtime Error

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

prev = None
ans = 0
for t in map(int, input().split()):
    if prev is not None:
        if t - prev < T:
            ans += t - prev
        else:
            ans += T
    prev = t
    print("ans:", ans)
ans += T


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

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

prev = None
ans = 0
for t in map(int, input().split()):
    if prev is not None:
        if t - prev < T:
            ans += t - prev
        else:
            ans += T
    prev = t
ans += T
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
N,T = map(int, input().split())
prev = 0
ans = 0
for i in range(N):
  t = int(input())
  if prev+T <= t:
    ans += T
  else:
    ans += (t - prev)
    prev = t

print(ans + T)
    

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

ans = 0
end = -1
start = -1
for x in t:
    if end < x:
        ans += (end - start)
        start = x
        end = x + T
    else:
        end = x + T

ans += (end - start)

print(ans)


Verdicts: Runtime Error

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
N,T = map(int,input().split())
t = list(map(int,input().split()))
cnt=0
ter=-1
for x in t:
  if(x>=ter):
    cnt+=1
    ter=x+T
print(cnt*T)


N,T = map(int,input().split())
t = list(map(int,input().split()))
cnt=0
ter=0
for x in t:
  if(x<=ter):
    cnt+=1
    ter=x+T
print(cnt*T)

N,T = map(int,input().split())
t = list(map(int,input().split()))
ans=0
ter=-1
for x in t:
  if(x>=ter):
    ans+=T
  else:
    ans+=T-(ter-x)
  ter=x+T

print(ans)


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: In a public bath, there is a shower which emits water for T seconds when the switch is pushed.  If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.  N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.  How long will the shower emit water in total?

Submission attempts (in order):
n,t=map(int,input().split())
k=1000000000
for i in map(int,input().split()):
  ans+=min(t,max(i-k,0))
  k=i
ans+=t
print(ans)

n,t=map(int,input().split())
ans=0
k=1000000000
for i in map(int,input().split()):
  ans+=min(t,max(i-k,0))
  k=i
ans+=t
print(ans)

Verdicts: Runtime Error

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
# ARC073D - Simple Knapsack (ABC060D)
from itertools import accumulate


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  
    for i in range(0, 2 * N, 2):
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    print(V, L)
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                for l in range(L[3]):
                    w = i * x + j * (x + 1) + k * (x + 2) + l * (x + 3)
                    if w > W:
                        break
                    v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                    ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

# ARC073D - Simple Knapsack (ABC060D)
from itertools import accumulate


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  
    for i in range(0, 2 * N, 2):
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                for l in range(L[3]):
                    w = i * x + j * (x + 1) + k * (x + 2) + l * (x + 3)
                    if w > W:
                        break
                    v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                    ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
n, w = map(int, input().split())
a = []
for _ in range(n):
    w_in, v_in = map(int, input().split())
    a.append([w_in, v_in])

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for j in range(w + 1):
    for i in range(n):
        w_in, v_in = a[i]
        if j + w_in <= w:
            dp[i + 1][j + w_in] = max(dp[i + 1][j + w_in], dp[i][j] + v_in)
            if i + 2 <= n:
                dp[i + 2][j + w_in] = max(dp[i + 2][j + w_in], dp[i + 1][j + w_in])
        dp[i + 2][j] = max(dp[i + 2][j], dp[i + 1][j])
print(max([max(d) for d in dp]))

from itertools import accumulate
n, w = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)
for _ in range(n - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0
for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if ((i) * w_0) + ((j) * (w_0 + 1)) + ((k) * (w_0 + 2)) + (((l) * (w_0 + 3))) <= w:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)

Verdicts: Runtime Error

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
n,w=map(int,input().split())
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))

dp=[0]*(w*2)
for w,v in WV:
    for i in range(w+1):
        try: dp[i]=max(dp[i],dp[i-w]+v)
        except:
            dp[i]=dp[i]


print(max(dp[:w+1]))

n,w=map(int,input().split())
from heapq import heappush,heappop
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))
dp={}
dp[0]=0
for w,v in WV:
    ndp=dp.copy()
    for i in ndp:
        if i+w>w:
            continue 
        temp=dp[i]
        try:
            use=dp[i+w]
            dp[i+w]+=max(temp+v-use,0)
        except:
            dp[i+w]=temp+v 
    
ans=[]
for i in dp:
    heappush(ans,-dp[i])

print(-heappop(ans))


n,w=map(int,input().split())
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))
dp={}
dp[0]=0
for w,v in WV:
    for i in JinA:
        if i+w>w:
            continue 
        temp=dp[i]
        try:
            use=dp[i+w]
            dp[i+w]+=max(temp+v-use,0)
        except:
            dp[i+w]=temp+v 
    
ans=[]
for i in dp:
    heappush(ans,-dp[i])

print(-heappop(ans))

from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


if __name__ == "__main__":
    main()


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
from itertools import accumulate
N, W = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)

for _ in range(n - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0

#print(v_list)

for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if (i * w_0) + (j * (w_0 + 1)) + (k * (w_0 + 2)) + (l * (w_0 + 3)) <= W:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)



from itertools import accumulate
N, W = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)

for _ in range(N - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0

#print(v_list)

for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if (i * w_0) + (j * (w_0 + 1)) + (k * (w_0 + 2)) + (l * (w_0 + 3)) <= W:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)



Verdicts: Runtime Error

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
N,W=map(int,input().split())
from collections import*
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for k,b in d.copy().items():
        if k+w<=W:
            d[k+w]=max(b,d[k]+v)
print(max(d.values()))


from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return print(max(d.values()))
N,W=map(int,input().split())   
d=defaultdict(int)
d[0]=0
if __name__=='__main__':
  Knapsack(N,W)

Verdicts: Wrong Answer

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
ints = input().split(" ")
N = int(ints[0])
maxW = int(ints[1])
ints = input().split(" ")
a = int(ints[0])
b = int(ints[1])
weight = [a, a+1, a+2, a+3] 
va = [[0,b],[0],[0],[0]]
for i in range(1, N):
	ins = input().split(" ")
	w = int(ins[0])
	v = int(ins[1])
	for j in range(0, 4):
		if w == weight[j]:
			va[j].append(v)
va.sort()
sum = [[0],[0],[0],[0]]
for j in range(0, 4):
	for i in range(1, len(va[j])):
		try:
			sum[j].append(sum[j][i-1] + va[j][i])
		except:
			pass
ans = 0
for i in range(0, len(va[0])):
	for j in range(0, len(va[1])):
		for k in range(0, len(va[2])):
			for l in range(0, len(va[3])):
				sumw = weight[0]*i + weight[1]*j +weight[2]*k + weight[3]*l
				if(sumw <= maxW):
					ans = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l],ans)
print(ans)

ints = input().split(" ")
N = int(ints[0])
maxW = int(ints[1])
ints = input().split(" ")
a = int(ints[0])
b = int(ints[1])
weight = [a, a+1, a+2, a+3] 
va = [[b],[],[],[]]
for i in range(1, N):
	ins = input().split(" ")
	w = int(ins[0])
	v = int(ins[1])
	for j in range(0, 4):
		if w == weight[j]:
			va[j].append(v)
for i in range(0, len(va)):
	va[i].sort(reverse=True)
	va[i].insert(0,0)
#print(va)
sum = [[0],[0],[0],[0]]
for j in range(0, 4):
	for i in range(1, len(va[j])):
		try:
			sum[j].append(sum[j][i-1] + va[j][i])
		except:
			pass
ans = 0
#print(sum)
for i in range(0, len(va[0])):
	for j in range(0, len(va[1])):
		for k in range(0, len(va[2])):
			for l in range(0, len(va[3])):
				sumw = weight[0]*i + weight[1]*j +weight[2]*k + weight[3]*l
				if(sumw <= maxW):
					ans = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l],ans)
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
from itertools import accumulate
N,W = map(int,input().split())
w = [[] for i in range(4)]
w1,v1 = map(int,input().split())
w[0].append(v1)
for i in range(N-1):
    wi,vi = map(int,input().split())
    w[wi-w1].append(vi)
num = []
for i in range(4):
    w[i].sort(reverse= 1)
    w[i] = [0]+list(accumulate(w[i]))
    num.append(len(w[i]))
ans = 0
for n1 in range(num[0]+1):
    for n2 in range(num[1]+1):
        for n3 in range(num[2]+1):
            for n4 in range(num[3]+1):
                wc = w1*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
                if wc <= W:
                    vc = w[0][n1]+w[1][n2]+w[2][n3]+w[3][n4]
                    ans = max(ans,vc)
print(ans)

from itertools import accumulate
N,W = map(int,input().split())
w = [[] for i in range(4)]
w1,v1 = map(int,input().split())
w[0].append(v1)
for i in range(N-1):
    wi,vi = map(int,input().split())
    w[wi-w1].append(vi)
num = []
for i in range(4):
    w[i].sort(reverse= 1)
    w[i] = [0]+list(accumulate(w[i]))
    num.append(len(w[i]))
ans = 0
for n1 in range(num[0]):
    for n2 in range(num[1]):
        for n3 in range(num[2]):
            for n4 in range(num[3]):
                wc = w1*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
                if wc <= W:
                    vc = w[0][n1]+w[1][n2]+w[2][n3]+w[3][n4]
                    ans = max(ans,vc)
print(ans)
        

Verdicts: Runtime Error

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
n, w = map(int, input().split())
di = dict()
m = 0
for _ in range(n):
  x,y = map(int, input().split())
  if x not in di:
    di[x] = []
  di[x].append(y)
for i in di:
  di[i].sort(reverse=True)
a,b,c,d = di.keys()
for i in range(len(di[a])):
  for j in range(len(di[b])):
    for k in range(len(di[c])):
      for l in range(len(di[d])):
        if i*a + j*b + k*c + l*d <= w:
          m = max(m, sum(di[a][:i+1] + di[b][:j+1] + di[c][:k+1] + di[d][:l+1]))
print(m)

n, w = map(int, input().split())
di = dict()
m = 0
for _ in range(n):
  x,y = map(int, input().split())
  if x not in di:
    di[x] = []
  di[x].append(y)
for i in di:
  di[i].sort(reverse=True)
a = min(di.keys())
b,c,d = a+1,a+2,a+3
for i in b,c,d:
  if i not in di:
    di[i] = []
for i in range(len(di[a])+1):
  for j in range(len(di[b])+1):
    for k in range(len(di[c])+1):
      for l in range(len(di[d])+1):
        if i*a + j*b + k*c + l*d <= w:
          m = max(m, sum(di[a][:i] + di[b][:j] + di[c][:k] + di[d][:l]))
print(m)

Verdicts: Runtime Error

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
N,W = map(int, input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

MINW = WV[0][0]

W0,W1,W2,W3 = [],[],[],[]
for w,v in WV:
    if w == MINW: W0.append(v)
    elif w == MINW + 1: W1.append(v)
    elif w == MINW + 2: W2.append(v)
    elif w == MINW + 3: W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)

W0 = [0] + W0
W0 = [0] + W1
W0 = [0] + W2
W0 = [0] + W3

from itertools import accumulate

W0 = list(accumulate(W0))
W1 = list(accumulate(W1))
W2 = list(accumulate(W2))
W3 = list(accumulate(W3))

ans = 0
for cnt0 in range(len(W0)):
    for cnt1 in range(len(W1)):
        for cnt2 in range(len(W2)):
            for cnt3 in range(len(W3)):
                SUMW = cnt0 * MINW
                SUMW += cnt1 * (MINW + 1)
                SUMW += cnt2 * (MINW + 2)
                SUMW += cnt3 * (MINW + 3)

                if SUMW <= W:
                    SUMV = W0[cnt0]
                    SUMV += W1[cnt1]
                    SUMV += W2[cnt2]
                    SUMV += W3[cnt3]
                    ans = max(ans, SUMV)

print(ans)

N,W = map(int, input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

MINW = WV[0][0]

W0,W1,W2,W3 = [],[],[],[]
for w,v in WV:
    if w == MINW: W0.append(v)
    elif w == MINW + 1: W1.append(v)
    elif w == MINW + 2: W2.append(v)
    elif w == MINW + 3: W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)

W0 = [0] + W0
W1 = [0] + W1
W2 = [0] + W2
W3 = [0] + W3

from itertools import accumulate

W0 = list(accumulate(W0))
W1 = list(accumulate(W1))
W2 = list(accumulate(W2))
W3 = list(accumulate(W3))

ans = 0
for cnt0 in range(len(W0)):
    for cnt1 in range(len(W1)):
        for cnt2 in range(len(W2)):
            for cnt3 in range(len(W3)):
                SUMW = cnt0 * MINW
                SUMW += cnt1 * (MINW + 1)
                SUMW += cnt2 * (MINW + 2)
                SUMW += cnt3 * (MINW + 3)

                if SUMW <= W:
                    SUMV = W0[cnt0]
                    SUMV += W1[cnt1]
                    SUMV += W2[cnt2]
                    SUMV += W3[cnt3]
                    ans = max(ans, SUMV)

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl()
a = [inpl() for _ in range(n)]
gds = [[0] for _ in range(4)]
a.sort()
a.sort(key = lambda x:x[1], reverse = True)
# print(a)
mi = a[0][0]
for i,(w,v) in enumerate(a):
    ind = w - mi
    gds[ind].append(v)
we = [i+mi for i in range(4)]
cnt = [0] * 4
for i in range(4):
    cnt[i] = len(gds[i])
    tmp = itertools.accumulate(gds[i])
    gds[i] = list(tmp)
# print(gds)
it = itertools.product(range(cnt[0]),range(cnt[1]),range(cnt[2]),range(cnt[3]))
res = 0
for ww in it:
    if sum(we[i]*ww[i] for i in range(4)) > W: continue
    now = sum(gds[i][ww[i]] for i in range(4))
    res = max(now, res)
print(res)

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl()
a = [inpl() for _ in range(n)]
gds = [[0] for _ in range(4)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort(key = lambda x:x[0])
# print(a)
mi = a[0][0]
for i,(w,v) in enumerate(a):
    ind = w - mi
    gds[ind].append(v)
we = [i+mi for i in range(4)]
cnt = [0] * 4
for i in range(4):
    cnt[i] = len(gds[i])
    tmp = itertools.accumulate(gds[i])
    gds[i] = list(tmp)
# print(gds)
it = itertools.product(range(cnt[0]),range(cnt[1]),range(cnt[2]),range(cnt[3]))
res = 0
for ww in it:
    if sum(we[i]*ww[i] for i in range(4)) > W: continue
    now = sum(gds[i][ww[i]] for i in range(4))
    res = max(now, res)
print(res)

Verdicts: Wrong Answer

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
n,w = map(int, input().split())
w4 = [[] for i in range(4)]
w1 = None
for i in range(n):
    ws, vs = map(int,input().split())
    if i == 0:
        w1 = ws
    ws -= w1
    w4[ws].append(vs)

for i in range(4):
    w4[i].sort(reverse=True)
    tmp = [0]
    for j in w4[i]:
        tmp.append(tmp[-1]+j)
    w4[i] = tmp
ans = 0
for i in range(len(w4[0])):
    for j in range(len(w4[1])):
        for k in range(len(w4[2])):
            for l in range(len(w4[3])):
                if w >= w1*(i+j+k+l) + j + 2*k + 3*l:
                    print(i,j,k,l)
                    ans = max(ans, w4[0][i]+w4[1][j]+w4[2][k]+w4[3][l])
print(ans)

n,w = map(int, input().split())
w4 = [[] for i in range(4)]
w1 = None
for i in range(n):
    ws, vs = map(int,input().split())
    if i == 0:
        w1 = ws
    ws -= w1
    w4[ws].append(vs)

for i in range(4):
    w4[i].sort(reverse=True)
    tmp = [0]
    for j in w4[i]:
        tmp.append(tmp[-1]+j)
    w4[i] = tmp
ans = 0
for i in range(len(w4[0])):
    for j in range(len(w4[1])):
        for k in range(len(w4[2])):
            for l in range(len(w4[3])):
                if w >= w1*(i+j+k+l) + j + 2*k + 3*l:
                    ans = max(ans, w4[0][i]+w4[1][j]+w4[2][k]+w4[3][l])
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Submission attempts (in order):
import collections
N, W = map(int, input().split())
wv = collections.defaultdict(list)
w = 0
for i in range(N):
    a, b = map(int, input().split())
    wv[a].append(b)
    if i == 0:
        w = a
s = [[0]*(len(wv[w+i])+1) for i in range(4)]

for i in range(4):
    wv[w + i].sort(reverse=True)
    for j, x in enumerate(wv[w + i]):
        s[i][j+1] = s[i][j] + x
ans = 0
L = len(wv[3])
for i in range(min(len(wv[w]), N)+1):
    tmp1 = s[0][i]
    weight1 = w * i
    if weight1 > W:
        break
    for j in range(min(len(wv[w+1])+1, N+1 - i)):

        tmp2 = tmp1 + s[1][j]
        weight2 = weight1 + (w+1)*j
        if weight2 > W:
            break
        for k in range(min(len(wv[w+2])+1, N+1 - i - j)):
            tmp3 = tmp2 + s[2][k]
            weight3 = weight2 + (w+2)*k
            if weight3 > W:
                break
            d = W - weight3

            ans = max(ans, tmp3 + s[3][min(L, d//(w+3))])
print(ans)


import collections
N, W = map(int, input().split())
wv = collections.defaultdict(list)
w = 0
for i in range(N):
    a, b = map(int, input().split())
    wv[a].append(b)
    if i == 0:
        w = a
s = [[0]*(len(wv[w+i])+1) for i in range(4)]

for i in range(4):
    wv[w + i].sort(reverse=True)
    for j, x in enumerate(wv[w + i]):
        s[i][j+1] = s[i][j] + x
ans = 0
L = len(wv[w+3])
for i in range(min(len(wv[w]), N)+1):
    tmp1 = s[0][i]
    weight1 = w * i
    if weight1 > W:
        break
    for j in range(min(len(wv[w+1])+1, N+1 - i)):

        tmp2 = tmp1 + s[1][j]
        weight2 = weight1 + (w+1)*j
        if weight2 > W:
            break
        for k in range(min(len(wv[w+2])+1, N+1 - i - j)):
            tmp3 = tmp2 + s[2][k]
            weight3 = weight2 + (w+2)*k
            if weight3 > W:
                break
            d = W - weight3

            ans = max(ans, tmp3 + s[3][min(L, d//(w+3))])
print(ans)


Verdicts: Runtime Error

Accepted
Problem: There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.  For each of these bags, you will paint one of the balls red, and paint the other blue.  Afterwards, the 2N balls will be classified according to color.  Then, we will define the following:    * R_{max}: the maximum integer written on a ball painted in red   * R_{min}: the minimum integer written on a ball painted in red   * B_{max}: the maximum integer written on a ball painted in blue   * B_{min}: the minimum integer written on a ball painted in blue  Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

Submission attempts (in order):
n = int(input())
x = []
y = []
xy = []
maxlist = []
minlist = []
amax = 0
amin = 10**10
case1 = 0
case2 = 0
for i in range(n):
    store = [int(j) for j in input().split(' ')]
    if store[0] < store[1]:
        store[0], store[1] = store[1], store[0]
    if store[0] == amax:
        maxlist.append(i)
    elif store[0] > amax:
        amax = store[0]
        maxlist = [i]
    if store[1] == amin:
        minlist.append(i)
    elif store[1] < amin:
        amin = store[1]
        minlist = [i]
    x.append(store[0])
    y.append(store[1])
    xy.extend(store)

case1 = (max(x) - min(x))*(max(y)-min(y))
for k in maxlist:
    if k in minlist:
        print(case1)
        exit()
for index in range(n):
    y[index] = [y[index], index]
y.sort()

bmax = y[n-1][0]
bmin = y[1][0]
check = True
minsum = 10**10
for i in range(0, n-1):
    if x[y[i][1]] > bmax:
        bmax = x[y[i][1]]
    if check and x[y[i][1]] <= y[i+1][0]:
        bmin = x[y[i][1]]
        check = False
    elif check:
        bmin = y[i+1][0]
    print(bmax, bmin)
    if minsum > bmax - bmin:
        minsum = bmax - bmin
case2 = minsum * (amax-amin)
print(min([case1, case2]))


n = int(input())
x = []
y = []
xy = []
maxlist = []
minlist = []
amax = 0
amin = 10**10
case1 = 0
case2 = 0
for i in range(n):
    store = [int(j) for j in input().split(' ')]
    if store[0] < store[1]:
        store[0], store[1] = store[1], store[0]
    if store[0] == amax:
        maxlist.append(i)
    elif store[0] > amax:
        amax = store[0]
        maxlist = [i]
    if store[1] == amin:
        minlist.append(i)
    elif store[1] < amin:
        amin = store[1]
        minlist = [i]
    x.append(store[0])
    y.append(store[1])
    xy.extend(store)

case1 = (max(x) - min(x)) * (max(y)-min(y))
for k in maxlist:
    if k in minlist:
        print(case1)
        exit()
for index in range(n):
    y[index] = [y[index], index]
y.sort()

bmax = y[n-1][0]
bmin = y[1][0]
xmin = 10**10
check = True
minsum = 10**10
for i in range(0, n-1):
    if x[y[i][1]] < xmin:
        xmin = x[y[i][1]]
    if x[y[i][1]] > bmax:
        bmax = x[y[i][1]]
    if check and xmin <= y[i+1][0]:
        bmin = xmin
        check = False
    elif check:
        bmin = y[i+1][0]
    if minsum > bmax - bmin:
        minsum = bmax - bmin
    if not check:
        break
case2 = minsum * (amax-amin)
print(min([case1, case2]))


Verdicts: Wrong Answer

Accepted
Problem: There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.  For each of these bags, you will paint one of the balls red, and paint the other blue.  Afterwards, the 2N balls will be classified according to color.  Then, we will define the following:    * R_{max}: the maximum integer written on a ball painted in red   * R_{min}: the minimum integer written on a ball painted in red   * B_{max}: the maximum integer written on a ball painted in blue   * B_{min}: the minimum integer written on a ball painted in blue  Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

Submission attempts (in order):
N = int(input())
balls = sorted(tuple(sorted(map(int,input().split()))) for i in range(N))

# Rmin=MIN, Bmax=MAX
maxmin = balls[-1][0]
minmin = balls[0][0]
maxmax = max(b[1] for b in balls)
minmax = min(b[1] for b in balls)

v1 = (maxmin-minmin)*(maxmax-minmax)

# Rmin=MIN, Rmax=MAX
best = float('inf')
cur_max = minmax
for b in balls:
  best = min(best, cur_max-b[0])
  cur_max = max(cur_max, b[1])

v2 = (maxmax-minmin)*best

print(min(v1,v2))

N = int(input())
balls = sorted(tuple(sorted(map(int,input().split()))) for i in range(N))

# Rmin=MIN, Bmax=MAX
maxmin = balls[-1][0]
minmin = balls[0][0]
maxmax = max(b[1] for b in balls)
minmax = min(b[1] for b in balls)

v1 = (maxmin-minmin)*(maxmax-minmax)

# Rmin=MIN, Rmax=MAX
best = float('inf')
cur_max = minmax
for b in balls:
  if b[0] > minmax:
    break
  best = min(best, cur_max-b[0])
  cur_max = max(cur_max, b[1])

v2 = (maxmax-minmin)*best

print(min(v1,v2))

N = int(input())
balls = sorted(tuple(sorted(map(int,input().split()))) for i in range(N))

# Rmin=MIN, Bmax=MAX
maxmin = balls[-1][0]
minmin = balls[0][0]
maxmax = max(b[1] for b in balls)
minmax = min(b[1] for b in balls)

v1 = (maxmin-minmin)*(maxmax-minmax)

# Rmin=MIN, Rmax=MAX
best = float('inf')
cur_max = maxmin
for b in balls:
  if b[0] > minmax:
    break
  best = min(best, cur_max-b[0])
  cur_max = max(cur_max, b[1])

v2 = (maxmax-minmin)*best

print(min(v1,v2))

N = int(input())
balls = sorted(tuple(sorted(map(int,input().split()))) for i in range(N))

# Rmin=MIN, Bmax=MAX
maxmin = balls[-1][0]
minmin = balls[0][0]
maxmax = max(b[1] for b in balls)
minmax = min(b[1] for b in balls)

v1 = (maxmin-minmin)*(maxmax-minmax)

# Rmin=MIN, Rmax=MAX
best = float('inf')
cur_max = maxmin
for b in balls:
  if b[0] > minmax:
    best = min(best, cur_max-minmax)
    break
  best = min(best, cur_max-b[0])
  cur_max = max(cur_max, b[1])
 
v2 = (maxmax-minmin)*best

print(min(v1,v2))

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.  For each of these bags, you will paint one of the balls red, and paint the other blue.  Afterwards, the 2N balls will be classified according to color.  Then, we will define the following:    * R_{max}: the maximum integer written on a ball painted in red   * R_{min}: the minimum integer written on a ball painted in red   * B_{max}: the maximum integer written on a ball painted in blue   * B_{min}: the minimum integer written on a ball painted in blue  Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

Submission attempts (in order):
# coding: utf-8



import heapq
N = int(input())

Rmax = 0
Rmin = 1000000001
Bmax = 0
Bmin = 1000000001

data = sorted([sorted(list(map(int, input().split()))) for i in range(N)],key=lambda x:x[0])

tempBlues = sorted([d[1] for d in data])
tempReds = [d[0] for d in data]
heapq.heapify(tempReds)
print(tempReds)

Rmin = data[0][0]
Rmax = data[N-1][0]
Bmax = max(tempBlues)
Bmin = min(tempBlues)

minValue = (Rmax - Rmin)*(Bmax - Bmin)
Bmin = Rmin

for i in range(N):
    heapMin = heapq.heappop(tempReds)
    if heapMin == data[i][0]:
        heapq.heappush(tempReds, data[i][1])
        if  data[i][1] > Rmax:
            Rmax = data[i][1]
        if (Rmax - tempReds[0])*(Bmax - Bmin) < minValue:
            minValue = (Rmax - tempReds[0])*(Bmax - Bmin)
    else:
        break

print(minValue)

# coding: utf-8



import heapq
N = int(input())

Rmax = 0
Rmin = 1000000001
Bmax = 0
Bmin = 1000000001

data = sorted([sorted(list(map(int, input().split()))) for i in range(N)],key=lambda x:x[0])

tempBlues = sorted([d[1] for d in data])
tempReds = [d[0] for d in data]
heapq.heapify(tempReds)

Rmin = data[0][0]
Rmax = data[N-1][0]
Bmax = max(tempBlues)
Bmin = min(tempBlues)

minValue = (Rmax - Rmin)*(Bmax - Bmin)
Bmin = Rmin

for i in range(N):
    heapMin = heapq.heappop(tempReds)
    if heapMin == data[i][0]:
        heapq.heappush(tempReds, data[i][1])
        if  data[i][1] > Rmax:
            Rmax = data[i][1]
        if (Rmax - tempReds[0])*(Bmax - Bmin) < minValue:
            minValue = (Rmax - tempReds[0])*(Bmax - Bmin)
    else:
        break

print(minValue)

Verdicts: Wrong Answer

Accepted
Problem: There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.  For each of these bags, you will paint one of the balls red, and paint the other blue.  Afterwards, the 2N balls will be classified according to color.  Then, we will define the following:    * R_{max}: the maximum integer written on a ball painted in red   * R_{min}: the minimum integer written on a ball painted in red   * B_{max}: the maximum integer written on a ball painted in blue   * B_{min}: the minimum integer written on a ball painted in blue  Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

Submission attempts (in order):
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
amin, amax, bmin, bmax = float("inf"), 0, float("inf"), 0
for i, j in xy:
    amin = min(amin, min(i, j))
    amax = max(amax, min(i, j))
    bmin = min(bmin, max(i, j))
    bmax = max(bmax, max(i, j))
print((amax - amin) * (bmax - bmin))

n = int(input())
lis = []
a, b = [], []
for i in range(n):
    X, Y = map(int, input().split())
    lis.append([min(X, Y), max(X, Y)])
    a.append(min(X, Y))
    b.append(max(X, Y))
lis.sort()
answer = (max(a) - min(a)) * (max(b) - min(b))
a_max, b_min = max(a), min(b)
current = float("inf")
for i in range(n):
    if lis[i][0] > b_min:
        current = min(current, a_max - b_min)
        break
    current = min(current, a_max - lis[i][0])
    a_max = max(a_max, lis[i][1])
print(min(answer, current * (max(b) - min(a))))

Verdicts: Wrong Answer

Accepted
Problem: You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Submission attempts (in order):
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

cnt = 1
x = []
for i in range(1, N):
    if A[i] >= A[i - 1]:
        cnt += 1
    else:
        x.append(cnt)
        cnt = 1
x.append(cnt)

ans = 0
i = 0
while i < len(x):
    if x[i] != 1:
        ans += 1
        i += 1
        continue
    j = i
    while j < len(x) and x[j] == 1:
        j += 1
    i = j
    ans += 1
print(ans)


import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

l = 0
r1 = 1
r2 = 1
ans = 0
while l < N:
    while r1 < N and d[r1] >= 0:
        r1 += 1
    while r2 < N and d[r2] <= 0:
        r2 += 1
    r = max(r1, r2)
    l = r
    ans += 1
    r1 = l + 1
    r2 = l + 1
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Submission attempts (in order):
n = int(input())
l = list(map(int, input().split()))

l1 = list()
for i in range(1, n):
    if l[i] > l[i-1]:
        l1.append(1)
    elif l[i] == l[i-1]:
        l1.append(0)
    else:
        l1.append(-1)

print(l1)
ans = 0

for i in range(n-1):
    if l1[i] != 0:
        c = l1[i]
        break

i = 0
while i <= n-3:
    if c*l1[i+1] == -1:
        ans += 1
        if i < n-3:
            c = l1[i+2]
        i += 2
    else:
        i += 1

print(ans + 1)

n = int(input())
l = list(map(int, input().split()))

i = 0
ans = 0
while i < n:
    j = i
    while j < n-1 and l[j] >= l[j+1]:
        j += 1
    k = i
    while k < n-1 and l[k] <= l[k+1]:
        k += 1
    i = max(j, k) + 1
    ans += 1
    #print(j, k)

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Submission attempts (in order):
N = int(input())

A = [int(_) for _ in input().split()]


for i in range(0, N):
    if A[0]>A[i]:
        flag = -1
        break

    if A[0]<A[i]:
        flag=1
        break


count=1
for j in range(0,N-1):
    if A[j]>A[j+1] and flag==1:
        count+=1
        flag=0

    if A[j]>A[j+1] and flag==0:
        flag=-1

    if A[j]<A[j+1] and flag==-1:
        count+=1
        flag=0
    if A[j]<A[j+1] and flag==0:
        flag=-1

    if A[i]==A[j+1]:
        flag=0    


print(count)


N = int (input())
A = [int(a) for a in input().split()]
d = 0
ans = 1
for i in range(1, N):
    if A[i-1] < A[i]:
        if d < 0:
            ans += 1
            d = 0
        elif d == 0:
            d = 1

    elif A[i-1] > A [i]:
        if d > 0:
            ans +=1
            d = 0
        elif d == 0:
            d = -1

print(ans)               


Verdicts: Wrong Answer

Accepted
Problem: You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Submission attempts (in order):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
def main():
    n, *a = map(int, read().split())
    a = deque(a)
    r = 1
    flag = False
    muki = 0
    char1 = a.popleft()
    while a:
        char = a.popleft()
        if flag:
            if muki == char > char1:
                continue
            else:
                r += 1
                flag = False
                char1 = char
        else:
            if char > char1:
                flag = True
                muki = 1
            elif char < char1:
                flag = True
                muki = 0
    print(r)

if __name__ == '__main__':
    main()


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
def main():
    n, *a = map(int, read().split())
    a = deque(a)
    r = 1
    flag = False
    muki = 0
    n1 = a.popleft()
    while a:
        n2 = a.popleft()
        if flag:
            if n1 < n2 and muki:
                n1 = n2
            elif n1 > n2 and not muki:
                n1 = n2
            elif n1 == n2:
                pass
            else:
                r += 1
                flag = False
                n1 = n2
        else:
            if n1 < n2:
                flag = True
                muki = 1
                n1 = n2
            elif n1 > n2:
                flag = True
                muki = 0
                n1 = n2
    print(r)

if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted
Problem: You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Submission attempts (in order):
def solve():
  n = int(input())
  a = list(map(int, input().split()))
  state, cut = -1, 0
  for i in range(n-1):
    #print(i, cut, state)
    if a[i] < a[i+1]:
      if state != 1:
        cut += 1
      state = 1
    else:
      if state != 0:
        cut += 1
      state = 0
  return 0
 
if __name__ == "__main__":
  solve()


def solve():
  n = int(input())
  a = list(map(int, input().split()))
  g, z = 0, 0
  cut = 1
  for i in range(n-1):
    if a[i+1] > a[i]:
      g += 1
    elif a[i+1] < a[i]:
      z += 1
    if g != 0 and z != 0:
      ans += 1
      g, z = 0, 0
  print(ans)
  return 0
 
if __name__ == "__main__":
  solve()


def solve():
  n = int(input())
  a = list(map(int, input().split()))
  g, z = 0, 0
  cut = 1
  for i in range(n-1):
    if a[i+1] > a[i]:
      g += 1
    elif a[i+1] < a[i]:
      z += 1
    if g != 0 and z != 0:
      cut += 1
      g, z = 0, 0
  print(cut)
  return 0
 
if __name__ == "__main__":
  solve()


Verdicts: Wrong Answer

Runtime Error

Accepted