Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

The Smallest Window I

  For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $S$, find the smallest sub-array size (smallest window length) where the sum of the sub-array is greater than or equal to $S$. If there is not such sub-array, report 0.

Constraints

 $1 \leq N \leq 10^5$ 

 $1 \leq S \leq 10^9$

 $1 \leq a_i \leq 10^4$

Input

The input is given in the following format.

$N$ $S$

$a_1$ $a_2$ ... $a_N$

Output

  Print the smallest sub-array size in a line.

Sample Input 1

6 4
1 2 1 2 3 2

Sample Output 1

2

Sample Input 2

6 6
1 2 1 2 3 2

Sample Output 2

3

Sample Input 3

3 7
1 2 3

Sample Output 3

0



Sample input:
6 4
1 2 1 2 3 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
INF = (sys.maxint)/3

def SmallestWindow(S, a_list):
	i = 0
	j = 0
	tmpS = 0
	res = INF
	while 1 :
		while tmpS < S and i <len(a_list)-1:
			i +=1
			tmpS += a_list[i]
		if (tmpS <S):
			break
		res = min (res, i-j)
		j += 1
		tmpS -=a_list[j]
	if res == INF:
		res = 0
	return res
		

def main():
	N, S = map(int, raw_input().split())
	a_list = map(int, raw_input().split())
	print SmallestWindow(S, a_list)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

ans = None
for window in range(1, n+1):
    sum_a = None
    for i in range(n-window):
        if sum_a == None:
            sum_a = sum(a[i:window])
        else:
            sum_a += a[i+window-1] - a[i-1]
        if sum_a >= s:
            ans = window
            break
    if ans != None: break

if ans == None: ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n,s = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(1,n):
    a[i] += a[i-1]
for i in range(n):
    if a[i] >= s:
        for j in range(i):
            v = j-1
            if a[i]-a[j] < s:
                break
        if ans == 0:
            ans = i-v
        else:
            ans = min(ans, i-v)
print(ans)

Submission status: Time Limit Exceeded

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

ans = None
for window in range(0, n):
    sum_a = None
    for i in range(n-window):
        if sum_a == None:
            sum_a = sum(a[i:window+1])
        else:
            sum_a += a[i+window] - a[i-1]
        if sum_a >= s:
            ans = window+1
            break
    if ans != None: break

if ans == None: ans = 0
print(ans)

Submission status: Time Limit Exceeded

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

ans = None
init_tmp = 0
for window in range(n):
    init_tmp += a[window]
    sum_a = init_tmp
    for i in range(n-window):
        if i != 0:
            sum_a += a[i+window] - a[i-1]
        if sum_a >= s:
            ans = window+1
            break
    if ans != None: break

if ans == None: ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
INF = (sys.maxint)/3

def SmallestWindow(S, a_list):
	i = 0
	j = 0
	tmpS = 0
	res = INF
	while 1 :
		while tmpS < S and i <len(a_list):
			tmpS += a_list[i]
			i = i+1
		if (tmpS <S):
			break
		res = min (res, i-j)
		tmpS -=a_list[j]
		j += 1
	if res == INF:
		res = 0
	return res
		

def main():
	N, S = map(int, raw_input().split())
	a_list = map(int, raw_input().split())
	print SmallestWindow(S, a_list)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from queue import deque

n, s = map(int, input().split())
q = deque()
t = 0
ans = 1e6
for a in map(int, input().split()):
    t += a
    q.append(a)
    if t < s:
        continue
    while t >= s:
        t -= q.popleft()
    ans = min(ans, len(q) + 1)
print(ans if ans < 1e6 else 0)

Submission status: Accepted

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

ans = float('inf')
l = 0
r = 0
sumv = 0
while True:
	while r < N and sumv < S:
		sumv += a[r]
		r += 1

	if sumv < S:
		break

	ans = min(ans,r-l)
	sumv -= a[l]
	l += 1

if ans == float('inf'):
	ans = 0
print(ans)

Submission status: Accepted

Solution code:
N,S = map(int, input().split())
As = list(map(int, input().split()))
i = 0
j = 0
sum = 0
m_l = float('inf')

while True:
	while j < N and sum < S:
		sum += As[j]
		j += 1
	
	if sum < S:
		break
	m_l = min(j-i, m_l)
	sum -= As[i]
	i += 1
	
"""
while j < N:
	sum += As[j]
	j += 1
	while i < j and sum :
		sum -= As[i]
		i += 1
		if sum >= S:
			continue
		m_l = min(j-i+1, m_l)
		break
"""
print(m_l if m_l != float('inf') else 0)

Submission status: Accepted

Solution code:
n,s = map(int, input().split())
a = list(map(int, input().split()))
ans = float("inf")
ma = 0
mi = 0
v = 0
for i in range(n):
    v += a[i]
    if v >= s:
        ma = i
        while v >= s:
            v -= a[mi]
            mi += 1
        ans = min(ans, ma-mi+2)
ans = ans if ans != float("inf") else 0
print(ans)

Submission status: Accepted

Solution code:
INF = 10**18

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

res = INF

rt = 0
s = 0

for lt in range(N):
    while rt < N and s < S:
        s += A[rt]
        rt += 1
    if s >= S:
        res = min(res, rt - lt)
    s -= A[lt]

print(res if res != INF else 0)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


N,S = map(int,input().split())
table = list(map(int,input().split()))

ans = BIG_NUM

left = 0
right = 0
tmp_sum = table[0]

while left < len(table):
    while True:
        if tmp_sum >= S:
            ans = min(ans,right-left+1)
            break
        if right == len(table)-1:
            break
        right += 1
        tmp_sum += table[right]

    if tmp_sum < S:
        break

    while True:
        if left > right:
            break
        tmp_sum -= table[left]
        left += 1
        if tmp_sum >= S:
            ans = min(ans,right-left+1)
        else:
            break
    right = max(right,left)


if ans == BIG_NUM:
    print("0")
else:
    print("%d"%(ans))

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string

setrecursionlimit(10**6)
input=stdin.readline

n,s=map(int,input().split())
a=[int(i) for i in input().split()]
nows=0
ans=2<<20
left=0
for right in range(n):
    nows+=a[right]
    while left<=right and right<n:
        if nows>=s:
            ans=min(ans,right-left+1)
            nows-=a[left]
            left+=1
        else: break
        #print(nows)
print(ans%(2<<20))

Submission status: Accepted

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

ans = float('INF')
total = 0
l = r = 0

while r < N:
    total += a[r]
    r += 1

    if total >= S:
        while total >= S:
            total -= a[l]
            l += 1
        ans = min(ans, r-l+1)

if ans == float('INF'): ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys


if __name__ == "__main__":
    N, S = map(lambda x: int(x), input().split())
    a = list(map(lambda x: int(x), input().split()))

    ans = sys.maxsize
    s = 0
    e = 0
    value = 0
    for idx in range(N):
        value += a[idx]
        if (S <= value):
            e = idx
            while (S <= value):
                value -= a[s]
                s += 1
            ans = min(ans, e - s + 2)
    ans = ans if ans != sys.maxsize else 0
    print(ans)

Submission status: Accepted

Solution code:
n,s=map(int,input().split( ))
a=list(map(int,input().split( )))
a.append(0)###
min=10000000000
sum_temp=0

i_first=0
i_next=0
while i_next<n:
    while sum_temp<s and i_next<=n:###
        sum_temp+=a[i_next]
        i_next+=1
    while sum_temp-a[i_first]>=s:
        sum_temp-=a[i_first]
        i_first+=1
    if i_next-i_first<min and sum_temp>=s:###
        min=i_next-i_first
    sum_temp-=a[i_first]
    i_first+=1
    if i_first>=n:
        break
if min<10000000000:
    print(min)
else:
    print(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Sliding Window - The Smallest Window I
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_A&lang=jp

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

total, l, r = 0, 0, 0
ans = float('inf')
while True:
    while r < N and total < S:
        total += A[r]
        r += 1
    if total < S:
        break
    ans = min(ans, r-l)
    total -= A[l]
    l += 1
print(ans if ans != float('inf') else 0)

Submission status: Accepted

Solution code:
from queue import deque

INF = 2**31-1
n, s = map(int, input().split())
A = list(map(int, input().split()))
q = deque()
t = 0
ans = INF
for a in A:
    t += a
    q.append(a)
    if t < s:
        continue
    while t >=s:
        t -=q.popleft()
    ans = min(ans,len(q)+1)
print(ans if ans < INF else 0)

Submission status: Accepted

Solution code:
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def LIR(n): return [LI() for i in range(n)]
def MI(): return map(int, input().split())
#1:set
#1_A
"""
n,q = map(int, input().split(" "))
group = [[i] for i in range(n)]
key = [i for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split(" "))
    if com == 0:
        if key[x] != key[y]:
            v = key[y]
            group[key[x]] = group[key[x]] + group[key[y]]
            for j in group[v]:
                key[j] = key[x]
            group[v] = []
    if com == 1:
        if key[x] == key[y]:
            print(1)
        else:
            print(0)
"""
#1_B
"""
def root(x,n):
    if par[x][0] == x:
        return [x,n+par[x][1]]
    return root(par[x][0],par[x][1])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx[0] == ry[0]:
        return
    par[rx][0] = ry[0]
    par[rx][1] += ry[1]
n,q = map(int, input().split(" "))
par = [[i,0] for i in range(n)]
for i in range(q):
    q = list(map(int, input().split(" ")))
    if q[0] == 0:

        if root(q[1],0) != root(q[])
"""
#2:range quary
#2_A
"""
n,q = map(int, input().split(" "))
k = 2**31-1
a = [float("inf") for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split(" "))
    if com == 0:
        a[x] = y
    else:
        mi = k
        for j in range(x, y+1):
            if a[j] == float("inf"):
                mi = min(mi, k)
            else:
                mi = min(mi,a[j])
        print(mi)
"""
#2_B

#2_C

#2_D

#2_E

#2_F

#2_G

#2_H

#2_I


#3:sliding window
#3_A
n,s = MI()
a = LI()
for i in range(1,n):
    a[i] += a[i-1]
a.insert(0,0)
l = 0
r = 0
ans = float("inf")
if a[1] >= s:
    print(1)
    quit()
while r < n:
    r += 1
    if a[r]-a[l] >= s:
        while a[r]-a[l] >= s and l < r:
            l += 1
        ans = min(ans, r-l+1)
if ans == float("inf"):
    print(0)
    quit()
print(ans)
#4:coordinate compression


#5:comulative sum
#5_A
"""
n,t = map(int, input().split(" "))
num = [0 for i in range(t)]
for i in range(n):
    l,r = map(int, input().split(" "))
    num[l] += 1
    if r < t:
        num[r] -= 1
for i in range(1,t):
    num[i] += num[i-1]
print(max(num))
"""

#5_B
"""
n = int(input())
lec = [[0 for i in range(1001)] for j in range(1001)]
max_x = 0
max_y = 0
for i in range(n):
    x,y,s,t = map(int, input().split(" "))
    lec[y][x] += 1
    lec[y][s] -= 1
    lec[t][x] -= 1
    lec[t][s] += 1
    max_x = max(max_x, s)
    max_y = max(max_y, t)

for i in range(max_y+1):
    for j in range(1, max_x+1):
        lec[i][j] += lec[i][j-1]

for i in range(1, max_y+1):
    for j in range(max_x+1):
        lec[i][j] += lec[i-1][j]

ans = 0
for i in range(max_y+1):
    for j in range(max_x+1):
        ans = max(ans, lec[i][j])

print(ans)
"""

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
*A, = map(int, input().split())

ans = N+1

v = t = 0
for s in range(N):
    while t < N and v < S:
        v += A[t]
        t += 1
    if S <= v:
        ans = min(ans, t-s)
    v -= A[s]
print(ans if ans < N+1 else 0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_3_A: The Smallest Window I
# binary search


def find(xs, size, s):
    sum_ = sum(xs[:size])
    if s <= sum_:
        return True
    for i in range(len(xs)-size):
        sum_ -= xs[i]
        sum_ += xs[i+size]
        if s <= sum_:
            return True
    return False


def run():
    n, s = [int(i) for i in input().split()]
    li = [int(i) for i in input().split()]

    if s > sum(li):
        print(0)
        return
    elif s < max(li):
        print(1)
        return

    i, j = 0, n
    while i+1 < j:
        # assert(not find(li, i, s))
        # assert(find(li, j, s))
        mid = (i + j) // 2
        # print(i, j, mid)
        if find(li, mid, s):
            j = mid
        else:
            i = mid

    print(j)


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
import sys
INF = (sys.maxint)/3

def SmallestWindow(S, a_list):
	i = 0
	j = 0
	tmpS = 0
	res = INF
	while 1 :
		while tmpS < S and i <len(a_list):
			i +=1
			tmpS += a_list[i]
		if (tmpS <S):
			break
		res = min (res, i-j)
		j += 1
		tmpS -=a_list[j]
	if res == INF:
		res = 0
	return res
		

def main():
	N, S = map(int, raw_input().split())
	a_list = map(int, raw_input().split())
	print SmallestWindow(S, a_list)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
A=map(int,raw_input().split())
list=[]
sum=0
S=1e6+1
for i in map(int,raw_input().split()):
    list.append(i)
    sum+=i
    if sum>A[1]:
        while sum>=A[1]:
            sum-=list.popleft()
        S=min(S,len(list)+1)
if S==1e6+1:
    print("0")
else:
    print(S)

Submission status: Runtime Error

Solution code:
A=map(int,raw_input().split())
list=[]
sum=0
S=1e6
for i in map(int,raw_input().split()):
    list.append(i)
    sum+=i
    if sum>A[1]:
        while sum>=A[1]:
            sum-=list.popleft()
        S=min(S,len(list)+1)
if S==1e6:
    print("0")
else:
    print(S)

Submission status: Runtime Error

Solution code:
N,S = map(int, input().split())
As = list(map(int, input().split()))
i = 0
j = 0
sum = 0
m_l = float('inf')
"""
while True:
	while j < N and sum < S:
		sum += As[j]
		j += 1
	
	if sum < S:
		break
	m_l = min(j-i, m_l)
	sum -= As[i]
	i += 1
	
"""
while j < N:
	sum += As[j]
	j += 1
	if sum < s:
		continue
	while i <= j and sum >= S:
		m_l = min(j-i, m_l)
		sum -= As[i]
		i += 1

print(m_l if m_l != float('inf') else 0)