Problem:


問題 B : Evacuation Route

問題文

日本では防災研究が盛んに行われており，近年その重要性がますます増している．
避難経路の評価も重要な研究のひとつである．
今回は直線状の通路の安全評価を行う．

通路は W 個のユニットに分けられており，一方の端のユニットからもう一方の端のユニットまで 0, &thinsp;1, &thinsp;2, &thinsp;…&thinsp;, &thinsp;W-1 の番号がつけられている．
通路内の各ユニットには，入口の扉，出口の扉，防火扉のいずれか1つが存在する．
入り口の扉，出口の扉，防火扉はそれぞれ通路内に複数個存在しうる．

この問題では時刻 t=0 で火災が発生したと想定する．
それにより，通路の外部にいて避難しようとしている人々が入口の扉を通じて通路へ入り，より安全な場所へ出るために出口の扉へ脱出しようとするものとする．
避難中のそれぞれの人は単位時刻ごとに 1 つのユニットを移動するか，今のユニットに留まることができる．
すなわち，時刻 t にある人がユニット i にいたとするとき，その人は時刻 t+1 ではユニット i-1, &thinsp;i, &thinsp; i+1 の3つの数字のうち 0 以上 W-1 以下であるものを選択し，その番号のユニットへ移動することができる．
防火扉があるユニットは，ある一定時刻以降になると完全に遮断されてしまい，避難中の人々はそのユニットに立ち入りできなくなる．また，そのユニット内に居た人々もそこから他のユニットに移動できなくなってしまう．

この問題における目的は，それぞれの扉の情報が与えられるので，避難中の人々が最適に行動した時に最大で何人が出口の扉へたどり着けるか計算することである．

通路の情報がW個の整数a_iで与えられる．

  
a_i = 0のとき，i 番目のユニットが出口の扉であることをあらわす．

  
a_i のとき，i 番目のユニットが防火扉により時間 |a_i| 以降出入りできなくなることを表す．

  
a_i > 0のとき，時刻 t=0,&thinsp;1,&thinsp;2,&thinsp;…&thinsp;,&thinsp;a_{i}-1 のそれぞれにおいて，ちょうど一人の人が i 番目のユニットに現れる．時刻 t に現れた人は，時刻 t+1 以降から移動を開始する．

なお，1つのユニットに複数の人々が存在してもかまわない．

出口の扉へたどり着ける最大の人数を求めよ．

入力形式

入力は以下の形式で与えられる

W
a_0 a_1 ... a_{W-1}

出力形式

最大人数を1行で出力せよ．

制約

1 ≤ W ≤ 10^5

|a_i| &thinsp; ≤ 10^4

入力値はすべて整数である．

入出力例

入力例 1

7
2 0 -2 3 2 -2 0

出力例 1

4

0, &thinsp; 3, &thinsp; 5番目のユニットに入り口の扉があり，
1, &thinsp; 6番目のユニットに出口の扉がある．

0番目のユニットからは，1番目のユニットへ２人出ることができる．

3番目のユニットからは，1番目のユニットへ１人出ることができる．

5番目のユニットからは，6番目のユニットへ１人出ることができる．

よって合わせて４人が出口へとたどり着ける．

入力例 2

4
1 1 1 1

出力例 2

0

出口がないので誰も脱出できない．

入力例 3

9
10 -10 10 -10 10 -10 10 -10 0

出力例 3

24  



Sample input:
7
2 0 -2 3 2 -2 0


Sample output:
4

Submission status: Wrong Answer

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    w = I()
    a = LI()
    b = [0] * w
    c = [0] * w
    ti = 0
    for i in range(w):
        k = a[i]
        if k == 0:
            ti = -inf
        elif k < 0:
            if ti < k:
                ti = k
        elif ti < 0:
            ti += 1
        b[i] = ti

    ti = 0
    for i in range(w-1,-1,-1):
        k = a[i]
        if k == 0:
            ti = -inf
        elif k < 0:
            if ti < k:
                ti = k
            elif ti < 0:
                ti += 1
        elif ti < 0:
            ti += 1
        c[i] = ti

    r = 0
    for i in range(w):
        if a[i] <= 0:
            continue
        r += min(abs(min(b[i], c[i])), a[i])

    return r




print(main())

Submission status: Wrong Answer

Solution code:
import sys
f = sys.stdin

#from io import StringIO
#f = StringIO('''7
#2 0 -2 3 2 -2 0''')

def calc(a,p,order):
    INF = 1000000
    limit = 0
    t = 0
    for i in range(len(a))[::order]:
        if a[i] == 0:
            limit = INF
            t = 0
        else:
            if a[i] < 0:
                limit = max(0, min(-a[i] - t, limit))
            else:
                p[i] = max(p[i], min(a[i], limit))
            limit -= 1
            t += 1

_ = int(f.readline())
a = list(map(int, f.readline().split()))
p = [0] * len(a)
calc(a,p,1)
calc(a,p,-1)

print(sum(p))

Submission status: Wrong Answer

Solution code:
def search_left(ind):
  doors = []
  for j in range(ind - 1, -1, -1):
    if alst[j] < 0:
     doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = alst[ind]
      for pos, lim in doors:
        ret = min(ret, lim - (ind - pos))
      ret = max(0, ret)
      return ret
  return 0

def search_right(ind):
  doors = []
  for j in range(ind + 1, w):
    if alst[j] < 0:
      doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = alst[ind]
      for pos, lim in doors:
        ret = min(ret, lim - (pos - ind))
      ret = max(0, ret)
      return ret
  return 0

def main():
  w = int(input())
  alst = list(map(int, input().split()))
  ans = 0
  for ind, a in enumerate(alst):
    if a > 0:
      ans += max(search_left(ind), search_right(ind))
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
W=input()
A=map(int,raw_input().split())
ans=0
for i in xrange(W):
    if A[i]<=0: continue
    lout = A[i]
    if 0 in A[:i]:
        for j in xrange(i-1,-1,-1):
            if A[j]==0:
                break
            elif A[j]<0:
                lout=max(0,min(lout,j-i-A[j]))
                if lout==0: break
    else:
        lout = 0
    rout = A[i]
    if 0 in A[i+1:]:
        for j in xrange(i+1,W+1):
            if A[j]==0:
                break
            elif A[j]<0:
                rout=max(0,min(rout,i-j-A[j]))
                if rout==0: break
    else:
        rout = 0
    ans+=max(lout,rout)
print ans

Submission status: Time Limit Exceeded

Solution code:
def search_left(ind, alst, a, w):
  doors = []
  for j in range(ind - 1, -1, -1):
    if alst[j] < 0:
     doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = a
      for pos, lim in doors:
        ret = min(ret, lim - (ind - pos))
      ret = max(0, ret)
      return ret
  return 0

def search_right(ind, alst, a, w):
  doors = []
  for j in range(ind + 1, w):
    if alst[j] < 0:
      doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = a
      for pos, lim in doors:
        ret = min(ret, lim - (pos - ind))
      ret = max(0, ret)
      return ret
  return 0

def main():
  w = int(input())
  alst = list(map(int, input().split()))
  ans = 0
  for ind, a in enumerate(alst):
    if a > 0:
      ans += max(search_left(ind, alst, a, w), search_right(ind, alst, a, w))
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl

def search_left(in_ind, alst, outs, doors):
  tmp = bl(outs, in_ind)
  if tmp == 0:
    return 0
  out_ind = outs[tmp - 1]

  right_door = bl(doors, in_ind) - 1
  if right_door < 0:
    return alst[in_ind]
  left_door = bl(doors, out_ind)
  
  ret = alst[in_ind]
  for door_ind in doors[left_door:right_door + 1]:
    if out_ind < door_ind < in_ind:
      ret = min(ret, -alst[door_ind] - (in_ind - door_ind))
  ret = max(0, ret)
  return ret

def search_right(in_ind, alst, outs, doors):
  tmp = bl(outs, in_ind)
  if tmp == len(outs):
    return 0
  out_ind = outs[tmp]

  right_door = bl(doors, out_ind) - 1
  if right_door < 0:
    return alst[in_ind]
  left_door = bl(doors, in_ind)

  ret = alst[in_ind]
  for door_ind in doors[left_door:right_door + 1]:
    if in_ind < door_ind < out_ind:
      ret = min(ret, -alst[door_ind] - (door_ind - in_ind))
  ret = max(0, ret)
  return ret

def main():
  w = int(input())
  alst = list(map(int, input().split()))
  outs = []
  ins = []
  doors = []
  for ind, a in enumerate(alst):
    if a > 0:
      ins.append(ind)
    elif a == 0:
      outs.append(ind)
    else:
      doors.append(ind)
  ans = 0
  for in_ind in ins:
    ans += max(search_left(in_ind, alst, outs, doors), search_right(in_ind, alst, outs, doors))
  print(ans)
main()

Submission status: Accepted

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    w = I()
    a = LI()
    b = [0] * w
    c = [0] * w
    ti = 0
    for i in range(w):
        k = a[i]
        if k == 0:
            ti = -inf
        elif k < 0:
            if ti < k:
                ti = k
            elif ti < 0:
                ti += 1
        elif ti < 0:
            ti += 1
        b[i] = ti

    ti = 0
    for i in range(w-1,-1,-1):
        k = a[i]
        if k == 0:
            ti = -inf
        elif k < 0:
            if ti < k:
                ti = k
            elif ti < 0:
                ti += 1
        elif ti < 0:
            ti += 1
        c[i] = ti

    r = 0
    for i in range(w):
        if a[i] <= 0:
            continue
        r += min(abs(min(b[i], c[i])), a[i])

    return r




print(main())

Submission status: Accepted

Solution code:
w = int(input())
alst = list(map(int, input().split()))
INF = 10 ** 20
acc = -INF
left = []
for i in range(w):
  a = alst[i]
  if a == 0:
    acc = INF
  elif a > 0:
    acc -= 1
  elif a < 0:
    acc = min(acc - 1, -a)
  left.append(acc)

acc = -INF
right = []
for i in range(w):
  a = alst[w - i - 1]
  if a == 0:
    acc = INF
  elif a > 0:
    acc -= 1
  elif a < 0:
    acc = min(acc - 1, -a)
  right.append(acc)
right.reverse()

print(sum([max(0, min(alst[i], max(left[i], right[i]))) for i in range(w)]))

Submission status: Accepted

Solution code:
from queue import PriorityQueue

class State:
  def __init__(self,index,time):
    self.index=index
    self.time=time
  def __lt__(self,state):
    return self.time>state.time

while 1:
  try: n=int(input())
  except: break
  a=list(map(int,input().split()))
  
  ts=[float("inf")]*n
  vis=[False]*n
  pq=PriorityQueue()
  for i in range(n):
    if a[i]==0:
      pq.put(State(i,int(1e9)))
  
  while pq.qsize():
    cur=pq.get()
    if cur.index<0 or n<=cur.index or vis[cur.index] or cur.time<0: continue
    vis[cur.index]=True
    if a[cur.index]<0:
      cur.time=min(cur.time,-a[cur.index]-1)
    ts[cur.index]=cur.time
    pq.put(State(cur.index-1,cur.time-1))
    pq.put(State(cur.index+1,cur.time-1))
  
  res=0
  for i in range(n):
    if a[i]>0 and vis[i]:
      res+=min(a[i],ts[i]+1)
  print(res)

Submission status: Accepted

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

ts=[0]*n
for indices in range(n),reversed(range(n)):
  t=0
  for i in indices:
    if a[i]==0: t=float("inf")
    if a[i]<0: t=min(t,-a[i])
    if a[i]>0: ts[i]=max(ts[i],min(a[i],t))
    t-=1
print(sum(ts))

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

def calc_limit(a,l,order):
    INF = 1000000
    limit = 0
    for i in range(len(a))[::order]:
        if a[i] == 0:
            limit = INF
        else:
            if a[i] < 0:
                limit = min(-a[i], limit)
            else:
                l[i] = max(l[i], limit)
            limit -= 1

_ = int(f.readline())
a = list(map(int, f.readline().split()))
l = [0] * len(a)
calc_limit(a,l,1)
calc_limit(a,l,-1)

print(sum(min(ai, li) for ai, li in zip(a,l) if ai > 0 ))

Submission status: Accepted

Solution code:
W=input()
A=map(int,raw_input().split())
L=[0]*W
R=[0]*W
now0=-1
for i in xrange(W):
    if A[i]==0:
        now0=i
        nowx=10**6
    if now0==-1: continue
    nowx-=1
    if A[i]<0: nowx=min(nowx,-A[i])
    if A[i]>0: L[i]=min(A[i],nowx)
now0=-1
for j in xrange(W):
    i = W-j-1
    if A[i]==0:
        now0=i
        nowx=10**6
    if now0==-1: continue
    nowx-=1
    if A[i]<0: nowx=min(nowx,-A[i])
    if A[i]>0: R[i]=min(A[i],nowx)
ans=0
for i in xrange(W):
    if max(L[i],R[i])>0: ans+=max(L[i],R[i])
print ans

Submission status: Runtime Error

Solution code:
def search_left(ind):
  doors = []
  for j in range(ind - 1, -1, -1):
    if alst[j] < 0:
     doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = alst[ind]
      for pos, lim in doors:
        ret = min(ret, lim - (ind - pos))
      ret = max(0, ret)
      return ret
  return 0

def search_right(ind):
  doors = []
  for j in range(ind + 1, w):
    if alst[j] < 0:
      doors.append((j, -alst[j]))
    if alst[j] == 0:
      ret = alst[ind]
      for pos, lim in doors:
        ret = min(ret, lim - (pos - ind))
      ret = max(0, ret)
      return ret
  return 0

def main():
  w = int(input())
  alst = list(map(int, input().split()))
  ans = 0
  for ind, a in enumerate(alst):
    if a > 0:
      ans += max(search_left(ind), search_right(ind))
  print(ans)
main()