結果
問題 | No.1433 Two color sequence |
ユーザー | chineristAC |
提出日時 | 2021-03-19 22:30:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 18,005 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 113,768 KB |
最終ジャッジ日時 | 2024-11-18 23:19:39 |
合計ジャッジ時間 | 4,562 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
def divisors(M):d=[]i=1while M>=i**2:if M%i==0:d.append(i)if i**2!=M:d.append(M//i)i=i+1return ddef popcount(x):x = x - ((x >> 1) & 0x55555555)x = (x & 0x33333333) + ((x >> 2) & 0x33333333)x = (x + (x >> 4)) & 0x0f0f0f0fx = x + (x >> 8)x = x + (x >> 16)return x & 0x0000007fdef eratosthenes(n):res=[0 for i in range(n+1)]prime=set([])for i in range(2,n+1):if not res[i]:prime.add(i)for j in range(1,n//i+1):res[i*j]=1return primedef factorization(n):res=[]for p in prime:if n%p==0:while n%p==0:n//=pres.append(p)if n!=1:res.append(n)return resdef euler_phi(n):res = nfor x in range(2,n+1):if x ** 2 > n:breakif n%x==0:res = res//x * (x-1)while n%x==0:n //= xif n!=1:res = res//n * (n-1)return resdef ind(b,n):res=0while n%b==0:res+=1n//=breturn resdef isPrimeMR(n):d = n - 1d = d // (d & -d)L = [2, 3, 5, 7, 11, 13, 17]for a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1: return 0t <<= 1return 1def findFactorRho(n):from math import gcdm = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retdef divisors(n):res = [1]prime = primeFactor(n)for p in prime:newres = []for d in res:for j in range(prime[p]+1):newres.append(d*p**j)res = newresres.sort()return resdef xorfactorial(num):#排他的論理和の階乗if num==0:return 0elif num==1:return 1elif num==2:return 3elif num==3:return 0else:x=baseorder(num)return (2**x)*((num-2**x+1)%2)+function(num-2**x)def xorconv(n,X,Y):if n==0:res=[(X[0]*Y[0])%mod]return resx=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]res1=xorconv(n-1,x,y)res2=xorconv(n-1,z,w)former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]former=list(map(lambda x:x%mod,former))latter=list(map(lambda x:x%mod,latter))return former+latterdef merge_sort(A,B):pos_A,pos_B = 0,0n,m = len(A),len(B)res = []while pos_A < n and pos_B < m:a,b = A[pos_A],B[pos_B]if a < b:res.append(a)pos_A += 1else:res.append(b)pos_B += 1res += A[pos_A:]res += B[pos_B:]return resclass UnionFindVerSize():def __init__(self, N):self._parent = [n for n in range(0, N)]self._size = [1] * Nself.group = Ndef find_root(self, x):if self._parent[x] == x: return xself._parent[x] = self.find_root(self._parent[x])stack = [x]while self._parent[stack[-1]]!=stack[-1]:stack.append(self._parent[stack[-1]])for v in stack:self._parent[v] = stack[-1]return self._parent[x]def unite(self, x, y):gx = self.find_root(x)gy = self.find_root(y)if gx == gy: returnself.group -= 1if self._size[gx] < self._size[gy]:self._parent[gx] = gyself._size[gy] += self._size[gx]else:self._parent[gy] = gxself._size[gx] += self._size[gy]def get_size(self, x):return self._size[self.find_root(x)]def is_same_group(self, x, y):return self.find_root(x) == self.find_root(y)class WeightedUnionFind():def __init__(self,N):self.parent = [i for i in range(N)]self.size = [1 for i in range(N)]self.val = [0 for i in range(N)]self.flag = Trueself.edge = [[] for i in range(N)]def dfs(self,v,pv):stack = [(v,pv)]new_parent = self.parent[pv]while stack:v,pv = stack.pop()self.parent[v] = new_parentfor nv,w in self.edge[v]:if nv!=pv:self.val[nv] = self.val[v] + wstack.append((nv,v))def unite(self,x,y,w):if not self.flag:returnif self.parent[x]==self.parent[y]:self.flag = (self.val[x] - self.val[y] == w)returnif self.size[self.parent[x]]>self.size[self.parent[y]]:self.edge[x].append((y,-w))self.edge[y].append((x,w))self.size[x] += self.size[y]self.val[y] = self.val[x] - wself.dfs(y,x)else:self.edge[x].append((y,-w))self.edge[y].append((x,w))self.size[y] += self.size[x]self.val[x] = self.val[y] + wself.dfs(x,y)class Dijkstra():class Edge():def __init__(self, _to, _cost):self.to = _toself.cost = _costdef __init__(self, V):self.G = [[] for i in range(V)]self._E = 0self._V = V@propertydef E(self):return self._E@propertydef V(self):return self._Vdef add_edge(self, _from, _to, _cost):self.G[_from].append(self.Edge(_to, _cost))self._E += 1def shortest_path(self, s):import heapqque = []d = [10**15] * self.Vd[s] = 0heapq.heappush(que, (0, s))while len(que) != 0:cost, v = heapq.heappop(que)if d[v] < cost: continuefor i in range(len(self.G[v])):e = self.G[v][i]if d[e.to] > d[v] + e.cost:d[e.to] = d[v] + e.costheapq.heappush(que, (d[e.to], e.to))return d#Z[i]:length of the longest list starting from S[i] which is also a prefix of S#O(|S|)def Z_algorithm(s):N = len(s)Z_alg = [0]*NZ_alg[0] = Ni = 1j = 0while i < N:while i+j < N and s[j] == s[i+j]:j += 1Z_alg[i] = jif j == 0:i += 1continuek = 1while i+k < N and k + Z_alg[k]<j:Z_alg[i+k] = Z_alg[k]k += 1i += kj -= kreturn Z_algclass BIT():def __init__(self,n):self.BIT=[0]*(n+1)self.num=ndef query(self,idx):res_sum = 0while idx > 0:res_sum += self.BIT[idx]idx -= idx&(-idx)return res_sum#Ai += x O(logN)def update(self,idx,x):while idx <= self.num:self.BIT[idx] += xidx += idx&(-idx)returnclass dancinglink():def __init__(self,n,debug=False):self.n = nself.debug = debugself._left = [i-1 for i in range(n)]self._right = [i+1 for i in range(n)]self.exist = [True for i in range(n)]def pop(self,k):if self.debug:assert self.exist[k]L = self._left[k]R = self._right[k]if L!=-1:if R!=self.n:self._right[L],self._left[R] = R,Lelse:self._right[L] = self.nelif R!=self.n:self._left[R] = -1self.exist[k] = Falsedef left(self,idx,k=1):if self.debug:assert self.exist[idx]res = idxwhile k:res = self._left[res]if res==-1:breakk -= 1return resdef right(self,idx,k=1):if self.debug:assert self.exist[idx]res = idxwhile k:res = self._right[res]if res==self.n:breakk -= 1return resclass SparseTable():def __init__(self,A,merge_func,ide_ele):N=len(A)n=N.bit_length()self.table=[[ide_ele for i in range(n)] for i in range(N)]self.merge_func=merge_funcfor i in range(N):self.table[i][0]=A[i]for j in range(1,n):for i in range(0,N-2**j+1):f=self.table[i][j-1]s=self.table[i+2**(j-1)][j-1]self.table[i][j]=self.merge_func(f,s)def query(self,s,t):b=t-s+1m=b.bit_length()-1return self.merge_func(self.table[s][m],self.table[t-2**m+1][m])class BinaryTrie:class node:def __init__(self,val):self.left = Noneself.right = Noneself.max = valdef __init__(self):self.root = self.node(-10**15)def append(self,key,val):pos = self.rootfor i in range(29,-1,-1):pos.max = max(pos.max,val)if key>>i & 1:if pos.right is None:pos.right = self.node(val)pos = pos.rightelse:pos = pos.rightelse:if pos.left is None:pos.left = self.node(val)pos = pos.leftelse:pos = pos.leftpos.max = max(pos.max,val)def search(self,M,xor):res = -10**15pos = self.rootfor i in range(29,-1,-1):if pos is None:breakif M>>i & 1:if xor>>i & 1:if pos.right:res = max(res,pos.right.max)pos = pos.leftelse:if pos.left:res = max(res,pos.left.max)pos = pos.rightelse:if xor>>i & 1:pos = pos.rightelse:pos = pos.leftif pos:res = max(res,pos.max)return resdef solveequation(edge,ans,n,m):#edge=[[to,dire,id]...]x=[0]*mused=[False]*nfor v in range(n):if used[v]:continuey = dfs(v)if y!=0:return Falsereturn xdef dfs(v):used[v]=Truer=ans[v]for to,dire,id in edge[v]:if used[to]:continuey=dfs(to)if dire==-1:x[id]=yelse:x[id]=-yr+=yreturn rclass Matrix():mod=10**9+7def set_mod(m):Matrix.mod=mdef __init__(self,L):self.row=len(L)self.column=len(L[0])self._matrix=Lfor i in range(self.row):for j in range(self.column):self._matrix[i][j]%=Matrix.moddef __getitem__(self,item):if type(item)==int:raise IndexError("you must specific row and column")elif len(item)!=2:raise IndexError("you must specific row and column")i,j=itemreturn self._matrix[i][j]def __setitem__(self,item,val):if type(item)==int:raise IndexError("you must specific row and column")elif len(item)!=2:raise IndexError("you must specific row and column")i,j=itemself._matrix[i][j]=valdef __add__(self,other):if (self.row,self.column)!=(other.row,other.column):raise SizeError("sizes of matrixes are different")res=[[0 for j in range(self.column)] for i in range(self.row)]for i in range(self.row):for j in range(self.column):res[i][j]=self._matrix[i][j]+other._matrix[i][j]res[i][j]%=Matrix.modreturn Matrix(res)def __sub__(self,other):if (self.row,self.column)!=(other.row,other.column):raise SizeError("sizes of matrixes are different")res=[[0 for j in range(self.column)] for i in range(self.row)]for i in range(self.row):for j in range(self.column):res[i][j]=self._matrix[i][j]-other._matrix[i][j]res[i][j]%=Matrix.modreturn Matrix(res)def __mul__(self,other):if type(other)!=int:if self.column!=other.row:raise SizeError("sizes of matrixes are different")res=[[0 for j in range(other.column)] for i in range(self.row)]for i in range(self.row):for j in range(other.column):temp=0for k in range(self.column):temp+=self._matrix[i][k]*other._matrix[k][j]res[i][j]=temp%Matrix.modreturn Matrix(res)else:n=otherres=[[(n*self._matrix[i][j])%Matrix.mod for j in range(self.column)] for i in range(self.row)]return Matrix(res)def __pow__(self,m):if self.column!=self.row:raise MatrixPowError("the size of row must be the same as that of column")n=self.rowres=Matrix([[int(i==j) for i in range(n)] for j in range(n)])while m:if m%2==1:res=res*selfself=self*selfm//=2return resdef __str__(self):res=[]for i in range(self.row):for j in range(self.column):res.append(str(self._matrix[i][j]))res.append(" ")res.append("\n")res=res[:len(res)-1]return "".join(res)class SegmentTree:def __init__(self, init_val, segfunc, ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.numfor i in range(n):self.tree[self.num + i] = init_val[i]for i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):k += self.numself.tree[k] = xwhile k > 1:self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])k >>= 1def query(self, l, r):res = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:res = self.segfunc(res, self.tree[r - 1])l >>= 1r >>= 1return resdef bisect_l(self,l,r,x):l += self.numr += self.numLmin = -1Rmin = -1while l<r:if l & 1:if self.tree[l] <= x and Lmin==-1:Lmin = ll += 1if r & 1:if self.tree[r-1] <=x:Rmin = r-1l >>= 1r >>= 1if Lmin != -1:pos = Lminwhile pos<self.num:if self.tree[2 * pos] <=x:pos = 2 * poselse:pos = 2 * pos +1return pos-self.numelif Rmin != -1:pos = Rminwhile pos<self.num:if self.tree[2 * pos] <=x:pos = 2 * poselse:pos = 2 * pos +1return pos-self.numelse:return -1import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N = int(input())S = input()A = li()R = [0] + [A[i] for i in range(N)]for i in range(1,N+1):if S[i-1]=="B":R[i] *= -1for i in range(1,N+1):R[i] += R[i-1]m = 0res = 0for i in range(1,N+1):res = max(res,R[i]-m)m = min(m,R[i])B = [0] + [A[i] for i in range(N)]for i in range(1,N+1):if S[i-1]=="R":B[i] *= -1for i in range(1,N+1):B[i] += B[i-1]m = 0for i in range(1,N+1):res = max(res,B[i]-m)m = min(m,B[i])print(res)