제출 #1344908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1344908		maximilianuggla	Feast (NOI19_feast)	Pypy 3	30 / 100	237 ms	228688 KiB

feast

def maxOfKIntervalls(nums, K: int) -> int:
    lowest = -10**20
    intervalls1 = []
    intervalls2 = []
    maxEnding1 = 0
    sum1 = lowest
    maxEnding2 = 0
    sum2 = lowest

    for e in nums:
        maxEnding1 = maxEnding1 + e
        maxEnding2 = maxEnding2 + e
        
        if maxEnding1 > sum1:
            sum1 = maxEnding1
            
        if maxEnding2 > sum2:
          sum2 = maxEnding2
          
        if maxEnding1 < 0:
            intervalls1.append(sum1)
            sum1 = lowest
            maxEnding1 = 0
            
        if maxEnding2 < sum2:
          intervalls2.append(sum2)
          sum2 = lowest
          maxEnding2 = 0
    
    intervalls1.append(sum1)
    intervalls2.append(sum2)    
    intervalls1.sort(reverse=True)
    intervalls2.sort(reverse=True)

    res1 = 0
    iterations = min(len(intervalls1), K)
    for k in range(iterations):
      if not intervalls1[k] < 0:
        res1 = res1 + intervalls1[k]
        
    res2 = 0
    iterations = min(len(intervalls2), K)
    for k in range(iterations):
      if not intervalls2[k] < 0:
        res2 = res2 + intervalls2[k]

    return max(res2, res1)


N, I = map(int, input().split())
numbers = list(map(int, input().split()))
print(maxOfKIntervalls(numbers, I))

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'feast.py'...

=======
  adding: __main__.pyc (deflated 36%)

=======

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29