글 읽기 - 반례를 찾아주세요..

quietquiet35 2년 전 0

반례를 이것저것 넣어 보았지만 잘 돌아가더라구요.. 4%에서 계속 틀렸다고 나옵니다. 혹시 반례를 찾아주실 수 있으실까요..부탁드립니다..(꾸벅)

N= int(input())
l = list(map(int,input().split()))

dp=[0]
candidate=[]
use=[]

def gaboza(x):
    if max(l) <= 0 : # 리스트 값이 전부 음수거나 0일때
        return print(max(l))


    for j in range(x): #맨 앞의 음수들 제거
        if l[j]>=0:
            break
        l[j]=0


    for i in range(x): # 중복된 양수 음수 정리
        if l[i]>=0:
            dp[-1]= dp[-1]+ l[i]
        elif l[i]<0:
            if l[i-1]>0:
                dp.append(l[i])
                dp.append(0)
            if l[i-1]<0:
                dp[-2]= dp[-2]+ l[i] 


    if len(dp) % 2 != 0: #dp 개수가 홀수일 때 고려
        dp.append(0)

    candidate.append(dp[0]) #사전에 정리
    if dp[0] + dp[1] > 0: 
        use.append(dp[0] + dp[1])
    else:
        use.append(0)

    for k in range(1,int(len(dp)/2)):  
        candidate.append(dp[2*k])
        candidate.append(dp[2*k]+use[-1])
        if dp[2*k] + dp[2*k+1] > 0:
            use.append(candidate[-1] + dp[2*k+1])
        elif dp[2*k] + dp[2*k+1] < 0:
            if use[-1]> dp[2*k] + dp[2*k+1]:
                use.append(use[-1]+ dp[2*k] + dp[2*k+1])
            else:
                use.append(0)
    print(max(candidate))

    

gaboza(N)

aiden0912 2년 전 1

-3 1 -2 3 -4 5 -7 7 -9 8 3 -4 -3 0 -7 10 -2 4 3 -123 2 2 2

Output:19

Answer:15

quietquiet35 2년 전 0

감사합니다..!!!

quietquiet35 2년 전 0

오류를 찾아 고쳤지만 시간초과가 뜨네요ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

반례를 찾아주세요..

quietquiet35 2년 전 0

aiden0912 2년 전 1

quietquiet35 2년 전 0

quietquiet35 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말