글 읽기 - [시간초과] 어떻게하면 더 시간을 줄일 수 있을까요..ᅲᅲ??

(追記) (追記ここまで)

[시간초과] 어떻게하면 더 시간을 줄일 수 있을까요..ᅲᅲ??

17498번 - 폴짝 게임

bae8416o 5년 전 0

더이상 줄일 수 있는 방법이 생각나지 않습니다.ᅲᅲᅲ

시간초과 떠버리네요 고수님들 헬프미!!!!

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
def move(x,y) : #move(x,y)는 arr[x][y] 에서 가질수 있는 최대의 값을 반환 한다.
 res = -1*2**32
 if x == N-1 :
 return 0
 if dp[x][y] != -1*2**32 :
 return dp[x][y]
 for nx in range(x+1,x+D+1) :
 dist = D-(nx-x)
 if y-dist < 0 :
 left = 0
 else :
 left = y-dist
 if y+dist >= M :
 right = M-1
 else:
 right = y+dist
 for ny in range(left,right+1) :
 if nx<N :
 res = max(res,arr[x][y]*arr[nx][ny]+move(nx,ny))
 dp[x][y]= res
 return res if res!= -1*2**32 else 0
if __name__ == '__main__' :
 N,M,D = map(int,input().strip().split())
 arr = [list(map(int,input().strip().split())) for _ in range(N)]
 dp = list([-1*2**32]*M for _ in range(N))
 ans = -1*2**32
 for y in range(M) :
 ans = max(ans,move(0,y))
 print(ans)

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

[시간초과] 어떻게하면 더 시간을 줄일 수 있을까요..ᅲᅲ??

bae8416o 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말