結果
| 問題 | No.2321 Continuous Flip |
| ユーザー |
👑  amentorimaru
|
| 提出日時 | 2023-02-16 01:29:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,434 ms / 2,000 ms |
| コード長 | 11,145 bytes |
| コンパイル時間 | 438 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 174,952 KB |
| 最終ジャッジ日時 | 2024-06-07 04:50:00 |
| 合計ジャッジ時間 | 36,020 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 168 ms
91,376 KB |
| testcase_01 | AC | 167 ms
91,008 KB |
| testcase_02 | AC | 168 ms
91,136 KB |
| testcase_03 | AC | 168 ms
91,392 KB |
| testcase_04 | AC | 1,269 ms
172,476 KB |
| testcase_05 | AC | 1,272 ms
171,128 KB |
| testcase_06 | AC | 1,197 ms
170,848 KB |
| testcase_07 | AC | 1,151 ms
170,512 KB |
| testcase_08 | AC | 1,222 ms
171,592 KB |
| testcase_09 | AC | 1,236 ms
171,308 KB |
| testcase_10 | AC | 1,202 ms
170,692 KB |
| testcase_11 | AC | 1,224 ms
171,384 KB |
| testcase_12 | AC | 1,293 ms
172,072 KB |
| testcase_13 | AC | 1,283 ms
171,284 KB |
| testcase_14 | AC | 1,209 ms
170,680 KB |
| testcase_15 | AC | 1,434 ms
174,952 KB |
| testcase_16 | AC | 1,262 ms
171,060 KB |
| testcase_17 | AC | 1,244 ms
170,396 KB |
| testcase_18 | AC | 1,212 ms
171,868 KB |
| testcase_19 | AC | 1,267 ms
172,084 KB |
| testcase_20 | AC | 1,287 ms
172,096 KB |
| testcase_21 | AC | 1,263 ms
170,692 KB |
| testcase_22 | AC | 1,348 ms
172,976 KB |
| testcase_23 | AC | 1,310 ms
171,956 KB |
| testcase_24 | AC | 416 ms
155,864 KB |
| testcase_25 | AC | 170 ms
91,008 KB |
| testcase_26 | AC | 392 ms
174,592 KB |
| testcase_27 | AC | 435 ms
159,744 KB |
| testcase_28 | AC | 919 ms
164,988 KB |
| testcase_29 | AC | 877 ms
165,756 KB |
| testcase_30 | AC | 922 ms
167,296 KB |
| testcase_31 | AC | 885 ms
164,992 KB |
| testcase_32 | AC | 865 ms
164,992 KB |
| testcase_33 | AC | 923 ms
166,652 KB |
ソースコード
from cmath import inf
from re import M
import sys
from collections import deque, Counter
from math import atan2, gcd, log10, pi, sqrt, ceil
from bisect import bisect, bisect_left, bisect_right, insort
from typing import Iterable, TypeVar, Union, Tuple, Iterator, List
# import bisect
from decimal import *
import time
import copy
import heapq
import itertools
import math
import random
from fractions import Fraction
from functools import lru_cache, partial, cmp_to_key
import operator
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
# import string
# import networkx as nx
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
mod2 = 998244353
# mod = 1 << 128
# mod = 10 ** 30 + 1
INF = 1 << 61
DIFF = 10 ** -9
DX = [1, 0, -1, 0, 1, 1, -1, -1]
DY = [0, 1, 0, -1, 1, -1, 1, -1]
def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for _ in range(N)]
class UnionFind:
def __init__(self,n):
self.parent=list(range(n))
self.size=[1]*n
def root(self,a):
if(self.parent[a]==a):return a
self.parent[a]=self.root(self.parent[a])
return self.parent[a]
def union(self,a,b):
pa=self.root(a)
pb=self.root(b)
if(pa==pb):return
if(self.size[pa]>self.size[pb]):pa,pb=pb,pa
self.parent[pa] = pb
self.size[pb]+=self.size[pa]
def same(self,a,b):
return self.root(a)==self.root(b)
class Dijkstra:
def __init__(self,n):
self.dist=[inf]*n
self.g = [list() for _ in range(n)]
def add(self,u,v,c):
self.g[u].append((v,c))
def calc(self,s):
self.dist[s]=0
q = [(0,s)]
while(len(q)>0):
d,v0 = heapq.heappop(q)
if(d>self.dist[v0]):continue
for (v1,c) in self.g[v0]:
if(self.dist[v1]<=d+c):continue
self.dist[v1]=d+c
heapq.heappush(q,(self.dist[v1],v1))
class SegTree:
def __init__(self,n):
self.size=1
while(self.size<n):self.size*=2
self.d=[self.unit()]*(self.size*2)
def unit(self):
return -1000000000000000
def calc(self,a,b):
return max(a,b)
def set(self,i,v):
self.forceset(i+self.size,v)
def forceset(self,i,v):
self.d[i]=v
while(i>1):
p=i//2
self.d[p]=self.calc(self.d[p*2],self.d[p*2+1])
i=p
#[l,r)
def get(self,i):
return self.d[self.size+i]
def query(self,l,r):
return self.queryImpl(l,r,0,self.size,1)
def queryImpl(self,l,r,ll,rr,v):
if(r<=ll or rr<=l):
return self.unit()
if(l<=ll and rr<=r):
return self.d[v]
m = (ll+rr)//2
vl = self.queryImpl(l,r,ll,m,v*2+0)
vr =self.queryImpl(l,r,m,rr,v*2+1)
return self.calc(vl,vr)
class LazySegTree:
def __init__(self,n):
self.size=1
while(self.size<n):self.size*=2
self.d=[self.unit()]*(self.size*2)
self.f=[self.id()]*self.size*2
def unit(self):
return -10**18
def id(self):
return -10**18
def calc(self,a,b):
return max(a,b)
def set(self,i,v):
self.forceset(i+self.size,v)
def forceset(self,i,v):
self.d[i]=v
while(i>1):
p=i//2
self.d[p]=self.calc(self.d[p*2],self.d[p*2+1])
i=p
#[l,r)
def get(self,i):
return self.query(i,i+1)
def query(self,l,r):
return self.queryImpl(l,r,0,self.size,1)
def queryImpl(self,l,r,ll,rr,v):
if(r<=ll or rr<=l):
return self.unit()
self.func(v)
if(l<=ll and rr<=r):
return self.d[v]
m = (ll+rr)//2
return self.calc(self.queryImpl(l,r,ll,m,v*2+0),self.queryImpl(l,r,m,rr,v*2+1))
def funcSet(self,l,r,fnc):
return self.funcSetImpl(l,r,fnc,0,self.size,1)
def funcSetImpl(self,l,r,fnc,ll,rr,v):
if(r<=ll or rr<=l):
return
if(l<=ll and rr<=r):
self.comp(v,fnc)
self.func(v)
self.forceset(v,self.d[v])
return
m = (ll+rr)//2
self.funcSetImpl(l,r,fnc,ll,m,v*2+0)
self.funcSetImpl(l,r,fnc,m,rr,v*2+1)
def func(self,i):
if(i<self.size):
self.comp(i*2+0,self.f[i])
self.comp(i*2+1,self.f[i])
self.d[i]=max(self.d[i],self.f[i])
self.f[i]=self.id()
def comp(self,i,fnc):
self.f[i]=max(self.f[i],fnc)
class BIT:
def __init__(self,n):
self.siz=1
while(self.siz<n):self.siz<<=1
self.b=[0]*self.siz
def update(self,k,v):
k+=1
while(k<=self.siz):
self.b[k-1]+=v
k+=k&-k
def query(self,k):
r = 0
k+=1
while(k>0):
r+=self.b[k-1]
k-=k&-k
return r
class MaxFlow:
def __init__(self,n):
self.g = [list() for _ in range(n)]
self.r = [list() for _ in range(n)]
self.f = [list() for _ in range(n)]
self.mc=[False]*n
self.size=n
self.q=[-1]*n
self.e=0
def add(self,u,v,c):
self.g[u].append(v)
self.g[v].append(u)
self.r[u].append(len(self.f[v]))
self.r[v].append(len(self.f[u]))
self.f[u].append(c)
self.f[v].append(0)
self.e+=1
def bfs(self,s,t):
self.depth=[-2]*self.size
self.depth[s]=0
self.q[0]=s
l=0
r=1
while(l<r):
v=self.q[l]
l+=1
for i in range(len(self.g[v])):
v2=self.g[v][i]
if(self.depth[v2]==-2 and self.f[v][i]>0):
self.depth[v2]=self.depth[v]+1
if(v2==t):return
self.q[r]=v2
r+=1
def dfs(self,v,t,f):
if(v==t):return f
r=0
for i in range(self.pg[v],len(self.g[v])):
self.pg[v]=i
v2=self.g[v][i]
i2=self.r[v][i]
if(self.f[v][i]==0 or self.depth[v]+1!=self.depth[v2]):continue
d=self.dfs(v2,t,min(f-r,self.f[v][i]))
if(d==0):continue
self.f[v][i]-=d
self.f[v2][i2]+=d
r+=d
if(r==f):break
self.depth[v]=self.size
return r
def flow(self,s,t):
r=0
while(1):
self.bfs(s,t)
if(self.depth[t]==-2):return r
if(self.depth[t]*self.depth[t]*2>self.e):break
self.pg=[0]*self.size
f = self.dfs(s,t,10**18)
if(f==0):break
r+=f
while(1):
self.fi=[False]*self.size
f = self.dfs2(s,t,10**18)
if(f==0):break
r+=f
return r
def mincut(self,v):
self.mc[v]=True
for i in range(len(self.g[v])):
v2,c,i2=self.g[v][i]
if(self.mc[v2] or self.f[v][i]==0):continue
self.mincut(v2)
def extgcd(a,b):
if(b==0):return (1,0)
u,v=extgcd(b,a%b)
return (v,u-a//b*v)
def convolution(f,g,m):
l=1
v=m-1
r=v
pg=3
if (m == 2):pg = 1;
if (m == 754974721):pg=11;
rpg=pow(pg,m-2,m)
p=list()
rp=list()
while(len(f)+len(g)>l+1):
l*=2
r//=2
p.append(pow(pg,r,m))
rp.append(pow(rpg,r,m))
while(p[-1]!=1):
p.append(p[-1]*p[-1]%m)
rp.append(rp[-1]*rp[-1]%m)
def FFT(ff,k,pl):
fl=len(ff)
if(fl==1):
return ff
hl=fl//2
ef=FFT(ff[::2],k+1,pl)
of=FFT(ff[1::2],k+1,pl)
r=[0]*fl
mul=1
for i in range(hl):
r[i+0]=(ef[i]+of[i]*mul)%m
r[i+hl]=(ef[i]-of[i]*mul)%m
mul=(mul*pl[k])%m
return r
ff=[0]*l
gg=[0]*l
for i in range(len(f)):
ff[i]=f[i]
for i in range(len(g)):
gg[i]=g[i]
ff=FFT(ff,0,p)
gg=FFT(gg,0,p)
for i in range(l):
ff[i]=(ff[i]*gg[i])%m
a=FFT(ff,0,rp)
rl=pow(l,m-2,m)
for i in range(l):
a[i]=a[i]*rl%m
return a
class scc:
def __init__(self,n):
self.g=[list() for _ in range(n)]
self.rg=[list() for _ in range(n)]
self.size=n
def add(self,u,v):
self.g[u].append(v)
self.rg[v].append(u)
def calc(self):
f=[-1]*self.size
nf=[0]
c=[False]*self.size
def dfs1(v):
c[v]=True
for tv in self.g[v]:
if(c[tv]):continue
dfs1(tv)
f[nf[0]]=v
nf[0]+=1
for i in range(self.size):
if(f[i]!=-1):continue
dfs1(i)
r=list()
c=[False]*self.size
nf[0]=0
def dfs2(v):
r[nf[0]].append(v)
c[v]=True
for tv in self.rg[v]:
if(c[v]):continue
dfs1(tv)
for i in range(self.size-1,-1,-1):
if(c[i]):continue
r.append(list())
dfs2(i)
nf[0]+=1
return r
def lower_bound(a,v):
l=-1
r=len(a)
while(l+1<r):
m=(l+r)//2
if(a[m]<v):
l=m
else:
r=m
return r
class Bimatching:
def __init__(self,n):
self.size=n
self.g=[[] for _ in range(n)]
self.to=[-1]*n
def add(self,u,v):
self.g[u].append(v)
def calc(self):
p=range(self.size)
c=[]
for i in p:
c.append((len(self.g[i]),i))
c.sort()
pl=[0]*self.size
for i in p:
pl[i]=c[i][1]
rev=[-1]*self.size
fr=[-1]*self.size
q=[0]*self.size
for i in pl:
q[0]=i
r=1
d=[0]*self.size
d[i]=1
for l in p:
if(l>=r):break
v=q[l]
for w in self.g[v]:
if(fr[w]!=-1):
if(d[fr[w]]==0):
d[fr[w]]=1
rev[fr[w]]=v
q[r]=fr[w]
r+=1
else:
r=0
vv=v
bw=w
for _ in p:
if(bw==-1):break
bw,self.to[vv]=self.to[vv],bw
fr[self.to[vv]]=vv
vv=rev[vv]
break
def main():
n,m,c=read_values()
a=read_list()
l=[0]*m
r=[0]*m
for i in range(m):
l[i],r[i]=read_values()
dj=Dijkstra(n+1)
for i in range(n):
dj.add(i+0,i+1,a[i])
dj.add(i+1,i+0,a[i])
for i in range(m):
dj.add(l[i]-1,r[i],c)
dj.add(r[i],l[i]-1,c)
dj.calc(0)
print(sum(a)-dj.dist[-1])
if __name__ == "__main__":
main()