結果

問題 No.1433 Two color sequence
ユーザー raven7959raven7959
提出日時 2021-08-21 11:40:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 421 ms / 2,000 ms
コード長 1,637 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 146,196 KB
最終ジャッジ日時 2024-04-23 03:25:10
合計ジャッジ時間 9,672 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
53,120 KB
testcase_01 AC 39 ms
53,208 KB
testcase_02 AC 38 ms
53,564 KB
testcase_03 AC 302 ms
116,460 KB
testcase_04 AC 292 ms
116,168 KB
testcase_05 AC 38 ms
53,340 KB
testcase_06 AC 38 ms
53,272 KB
testcase_07 AC 38 ms
54,484 KB
testcase_08 AC 332 ms
146,084 KB
testcase_09 AC 416 ms
145,560 KB
testcase_10 AC 390 ms
144,936 KB
testcase_11 AC 400 ms
144,972 KB
testcase_12 AC 398 ms
145,456 KB
testcase_13 AC 413 ms
145,464 KB
testcase_14 AC 406 ms
145,668 KB
testcase_15 AC 398 ms
145,940 KB
testcase_16 AC 407 ms
146,008 KB
testcase_17 AC 421 ms
146,196 KB
testcase_18 AC 415 ms
145,604 KB
testcase_19 AC 386 ms
145,848 KB
testcase_20 AC 401 ms
145,672 KB
testcase_21 AC 405 ms
145,600 KB
testcase_22 AC 408 ms
145,652 KB
testcase_23 AC 402 ms
145,588 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import accumulate
from math import inf
N=int(input())
S=input()
A=list(map(int,input().split()))
L=[0]*(N+1)
for i in range(N):
  if S[i]=="R":
    L[i+1]=A[i]
  else:
    L[i+1]=-A[i]
LA=list(accumulate(L))
class segtree():
  n=1
  size=1
  log=2
  d=[0]
  op=None
  e=10**15
  def update(self,k):
    self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
  def __init__(self,V,OP,E): #初期値(配列),演算,単位元で初期化
    self.n=len(V)
    self.op=OP
    self.e=E
    self.log=(self.n-1).bit_length()
    self.size=1<<self.log
    self.d=[E for i in range(2*self.size)]
    for i in range(self.n):
      self.d[self.size+i]=V[i]
    for i in range(self.size-1,0,-1):
      self.update(i)
  def set(self,p,x): #1点更新
    assert 0<=p and p<self.n
    p+=self.size
    self.d[p]=x
    for i in range(1,self.log+1):
      self.update(p>>i)
  def get(self,p): #1点取得
    assert 0<=p and p<self.n
    return self.d[p+self.size]
  def prod(self,l,r): #区間取得
    assert 0<=l and l<=r and r<=self.n
    sml=self.e
    smr=self.e
    l+=self.size
    r+=self.size
    while(l<r):
      if (l&1):
        sml=self.op(sml,self.d[l])
        l+=1
      if (r&1):
        smr=self.op(self.d[r-1],smr)
        r-=1
      l>>=1
      r>>=1
    return self.op(sml,smr)
  def all_prod(self): #全区間取得
    return self.d[1]
def MIN(x,y):
  return min(x,y)
def MAX(x,y):
  return max(x,y)
seg_min=segtree(LA,MIN,inf)
seg_max=segtree(LA,MAX,-inf)
ans_min=0
ans_max=0
for i in range(1,N+1):
  ans_min=min(ans_min,LA[i]-seg_max.prod(0,i))
  ans_max=max(ans_max,LA[i]-seg_min.prod(0,i))
print(max(-ans_min,ans_max))
0