제출 #1347596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1347596		maximilianuggla	Feast (NOI19_feast)	Pypy 3	22 / 100	223 ms	252412 KiB

feast

from collections import deque

class Intervall:
    def __init__(self, sum, start, end):
        self.sum = sum
        self.s = start
        self.e = end

    def __eq__(self, other):
      return self.s <= other.s <= self.e or self.s <= other.e <= self.e
    
    def __hash__(self):
      return hash((self.sum, self.s, self.e))

def maxOfKIntervalls(nums, K: int) -> int:
    lowest = -10**20
    intervalls = []
    maxEnding1 = 0
    start1 = 0
    end1 = 0
    sum1 = lowest
    maxEnding2 = 0
    start2 = 0
    end2 = 0
    sum2 = lowest

    for i in range(len(nums)):
        maxEnding1 = maxEnding1 + nums[i]
        maxEnding2 = maxEnding2 + nums[i]
        
        if maxEnding1 > sum1 and maxEnding1 > 0:
            sum1 = maxEnding1
            end1 = i
            
        if maxEnding2 > sum2 and maxEnding2 > 0:
          sum2 = maxEnding2
          end2 = i
          
        if maxEnding1 < 0:
            if sum1 > 0:
                intervalls.append(Intervall(sum1, start1, end1))
            sum1 = lowest
            maxEnding1 = 0
            start1 = i+1
            
        if maxEnding2 < sum2:
            if sum2 > 0:
                intervalls.append(Intervall(sum2, start2, end2))
            sum2 = lowest
            maxEnding2 = 0
            start2 = i+1
    if sum1 > 0:
        intervalls.append(Intervall(sum1, start1, end1))
    if sum2 > 0:
        intervalls.append(Intervall(sum2, start2, end2))    
    intervalls.sort(key=lambda x: (-x.sum, x.e-x.s))
    maxedIntervalls = set()
    i = 0
    while len(maxedIntervalls) < K and i < len(intervalls):
        maxedIntervalls.add(intervalls[i])
        i += 1
    
    res = 0
    for intervall in maxedIntervalls:
       res += intervall.sum

    return res


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

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

Compiling 'feast.py'...

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

=======

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