結果
| 問題 | No.2328 Build Walls |
| ユーザー |
👑  amentorimaru
|
| 提出日時 | 2023-05-28 14:51:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,476 ms / 3,000 ms |
| コード長 | 11,622 bytes |
| コンパイル時間 | 694 ms |
| コンパイル使用メモリ | 82,444 KB |
| 実行使用メモリ | 316,700 KB |
| 最終ジャッジ日時 | 2024-06-08 06:21:39 |
| 合計ジャッジ時間 | 21,348 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 147 ms
91,436 KB |
| testcase_01 | AC | 144 ms
91,008 KB |
| testcase_02 | AC | 143 ms
91,392 KB |
| testcase_03 | AC | 144 ms
91,264 KB |
| testcase_04 | AC | 145 ms
91,136 KB |
| testcase_05 | AC | 137 ms
91,256 KB |
| testcase_06 | AC | 143 ms
91,264 KB |
| testcase_07 | AC | 139 ms
91,276 KB |
| testcase_08 | AC | 138 ms
91,204 KB |
| testcase_09 | AC | 139 ms
91,136 KB |
| testcase_10 | AC | 140 ms
91,136 KB |
| testcase_11 | AC | 135 ms
91,136 KB |
| testcase_12 | AC | 138 ms
91,264 KB |
| testcase_13 | AC | 442 ms
161,536 KB |
| testcase_14 | AC | 516 ms
147,456 KB |
| testcase_15 | AC | 460 ms
136,704 KB |
| testcase_16 | AC | 244 ms
100,096 KB |
| testcase_17 | AC | 467 ms
141,056 KB |
| testcase_18 | AC | 191 ms
92,672 KB |
| testcase_19 | AC | 192 ms
97,536 KB |
| testcase_20 | AC | 217 ms
96,000 KB |
| testcase_21 | AC | 318 ms
127,488 KB |
| testcase_22 | AC | 672 ms
175,744 KB |
| testcase_23 | AC | 1,180 ms
263,936 KB |
| testcase_24 | AC | 1,137 ms
255,232 KB |
| testcase_25 | AC | 1,142 ms
262,436 KB |
| testcase_26 | AC | 1,009 ms
237,312 KB |
| testcase_27 | AC | 1,081 ms
250,928 KB |
| testcase_28 | AC | 403 ms
144,120 KB |
| testcase_29 | AC | 1,219 ms
264,004 KB |
| testcase_30 | AC | 728 ms
222,976 KB |
| testcase_31 | AC | 624 ms
212,352 KB |
| testcase_32 | AC | 1,064 ms
249,308 KB |
| testcase_33 | AC | 1,476 ms
316,700 KB |
| testcase_34 | AC | 683 ms
225,728 KB |
| testcase_35 | AC | 1,355 ms
289,408 KB |
| testcase_36 | AC | 138 ms
91,264 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 fractions
import time
import copy
import heapq
import itertools
import bisect
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 0
def calc(self,a,b):
return 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():
h,w=read_values()
a=[list() for _ in range(h-2)]
for i in range(h-2):
a[i]=read_list()
dj=Dijkstra((h-2)*w+2)
s=(h-2)*w
g=s+1
d=[(1,-1),(1,0),(1,1),(0,-1),(0,1),(-1,-1),(-1,0),(-1,1)]
for i in range(h-2):
for j in range(w):
for dx,dy in d:
nx=i+dx
ny=j+dy
if ny<0 or nx<0 or nx >= h-2:
continue
if ny==w:
dj.add(i*w+j,g,0)
else:
if(a[nx][ny]<0):
continue
dj.add(i*w+j,nx*w+ny,a[nx][ny])
for i in range(h-2):
if(a[i][0]<0):
continue
dj.add(s,i*w,a[i][0])
dj.calc(s)
if(dj.dist[g]<10**15):
print(dj.dist[g])
else:
print(-1)
if __name__ == "__main__":
main()