#774408 (Python3) No.655 E869120 and Good Triangles

提出ソース

結果

問題	No.655 E869120 and Good Triangles
ユーザー	vwxyz
提出日時	2022-06-29 04:36:08
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	TLE
実行時間	-
コード長	7,113 bytes
コンパイル時間	542 ms
コンパイル使用メモリ	13,568 KB
実行使用メモリ	821,484 KB
最終ジャッジ日時	2024-11-22 00:34:10
合計ジャッジ時間	46,009 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	43 ms 12,416 KB
testcase_01	AC	43 ms 12,416 KB
testcase_02	AC	43 ms 12,288 KB
testcase_03	AC	43 ms 12,672 KB
testcase_04	AC	42 ms 12,544 KB
testcase_05	AC	42 ms 12,672 KB
testcase_06	AC	46 ms 12,544 KB
testcase_07	AC	42 ms 12,416 KB
testcase_08	AC	42 ms 12,416 KB
testcase_09	AC	42 ms 12,672 KB
testcase_10	TLE	-
testcase_11	MLE	-
testcase_12	MLE	-
testcase_13	MLE	-
testcase_14	MLE	-
testcase_15	MLE	-
testcase_16	MLE	-
testcase_17	MLE	-
testcase_18	MLE	-
testcase_19	MLE	-
testcase_20	MLE	-
testcase_21	MLE	-
testcase_22	MLE	-
testcase_23	MLE	-
testcase_24	MLE	-
testcase_25	MLE	-
testcase_26	MLE	-
testcase_27	MLE	-
testcase_28	MLE	-
testcase_29	MLE	-
testcase_30	AC	96 ms 12,288 KB
testcase_31	AC	47 ms 12,672 KB
testcase_32	AC	47 ms 12,416 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        self.inf=inf
        if graph:
            self.graph=graph
            self.edges=[]
            for i in range(self.V):
                if self.weighted:
                    for j,d in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j,d))
                else:
                    for j in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j))
        else:
            self.edges=edges
            self.graph=[[] for i in range(self.V)]
            if weighted:
                for i,j,d in self.edges:
                    self.graph[i].append((j,d))
                    if not self.directed:
                        self.graph[j].append((i,d))
            else:
                for i,j in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        seen[s]=True
        if bfs_tour:
            bt=[s]
        if linked_components:
            lc=[s]
        if parents:
            ps=[None]*self.V
        if unweighted_dist or bipartite_graph:
            uwd=[self.inf]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[self.inf]*self.V
            wd[s]=0
        queue=deque([s])
        while queue:
            x=queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    y,d=y
                if not seen[y]:
                    seen[y]=True
                    queue.append(y)
                    if bfs_tour:
                        bt.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y]=x
                    if unweighted_dist or bipartite_graph:
                        uwd[y]=uwd[x]+1
                    if weighted_dist:
                        wd[y]=wd[x]+d
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if uwd[i]==self.inf or uwd[j]==self.inf:
                    continue
                if not uwd[i]%2^uwd[j]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if uwd[x]==self.inf:
                        continue
                    bg[uwd[x]%2].append(x)
        retu=()
        if bfs_tour:
            retu+=(bt,)
        if bipartite_graph:
            retu+=(bg,)
        if linked_components:
            retu+=(lc,)
        if parents:
            retu+=(ps,)
        if unweighted_dist:
            retu+=(uwd,)
        if weighted_dist:
            retu+=(wd,)
        if len(retu)==1:
            retu=retu[0]
        return retu
class Cumsum:
    def __init__(self,lst,mod=0):
        self.N=len(lst)
        self.mod=mod
        self.cumsum=[0]*(self.N+1)
        self.cumsum[0]=0
        for i in range(1,self.N+1):
            self.cumsum[i]=self.cumsum[i-1]+lst[i-1]
            if self.mod:
                self.cumsum[i]%=self.mod

    def __getitem__(self,i):
        if type(i)==int:
            if 0<=i<self.N:
                a,b=i,i+1
            elif -self.N<=i<0:
                a,b=i+self.N,i+self.N+1
            else:
                raise IndexError('list index out of range')
        else:
            a,b=i.start,i.stop
            if a==None or a<-self.N:
                a=0
            elif self.N<=a:
                a=self.N
            elif a<0:
                a+=self.N
            if b==None or self.N<=b:
                b=self.N
            elif b<-self.N:
                b=0
            elif b<0:
                b+=self.N
        s=self.cumsum[b]-self.cumsum[a]
        if self.mod:
            s%=self.mod
        return s

    def __setitem__(self,i,x):
        if -self.N<=i<0:
            i+=self.N
        elif not 0<=i<self.N:
            raise IndexError('list index out of range')
        self.cumsum[i+1]=self.cumsum[i]+x
        if self.mod:
            self.cumsum[i+1]%=self.mod

    def __str__(self):
        lst=[self.cumsum[i+1]-self.cumsum[i] for i in range(self.N)]
        if self.mod:
            for i in range(self.N):
                lst[i]%=self.mod
        return "["+", ".join(map(str,lst))+"]"

N,K,P=map(int,readline().split())
points=[(i,j) for i in range(N) for j in range(i+1)]
idx={points[i]:i+1 for i in range(len(points))}
edges=[]
for i in range(N):
    for j in range(i):
        edges.append((idx[(i,j)],idx[(i,j+1)]))
        edges.append((idx[(i,j+1)],idx[(i,j)]))
for i in range(N-1):
    for j in range(i+1):
        edges.append((idx[(i,j)],idx[(i+1,j)]))
        edges.append((idx[(i,j)],idx[(i+1,j+1)]))
        edges.append((idx[(i+1,j)],idx[(i,j)]))
        edges.append((idx[(i+1,j+1)],idx[(i,j)]))
for _ in range(K):
    x,y=map(int,readline().split())
    x-=1;y-=1
    edges.append((0,idx[(x,y)]))
G=Graph(len(points)+1,edges=edges,directed=True)
dist=G.SIV_BFS(0,unweighted_dist=True)
A=[[None]*(i+1) for i in range(N)]
for i,(x,y) in enumerate(points,1):
    A[x][y]=dist[i]-1
AL=[[A[i][j] for j in range(i+1)] for i in range(N)]
AR=[[A[i][j] for j in range(i+1)] for i in range(N)]
for i in range(1,N):
    for j in range(i):
        AL[i][j]+=AL[i-1][j]
for i in range(1,N):
    for j in range(1,i+1):
        AR[i][j]+=AR[i-1][j-1]
for i in range(N):
    A[i]=Cumsum(A[i])
ans=0
dp=[[(0,0)]*(i+1) for i in range(N)]
for i in range(N):
    for j in range(i+1):
        ii,s=dp[i][j]
        while ii<N and s<P:
            s+=A[ii][j:j-i+ii+1]
            ii+=1
        dp[i][j]=(ii,s)
        if i!=N-1:
            dp[i+1][j]=max(dp[i+1][j],(ii,s-(AR[ii-1][j-i+ii-1]-(AR[i-1][j-1] if i and j else 0))))
            dp[i+1][j+1]=max(dp[i+1][j+1],(ii,s-(AL[ii-1][j]-(AL[i-1][j] if i and i!=j else 0))))
ans=0
for i in range(N):
    for j in range(i+1):
        if dp[i][j][1]>=P:
            ans+=N-dp[i][j][0]+1
print(ans)

yukicoder

結果

テストケース

ソースコード