SRM588 Div2 500

GUMIAndSongsDiv2.py

import itertools


class GUMIAndSongsDiv2:
    def maxSongs(self, duration, tone, T):
        duration_tones = []
        for i, d in enumerate(duration):
            duration_tones.append((tone[i], d))

        duration_tones.sort()
        n = 0
        for i in xrange(1, len(duration_tones) + 1):
            for duration_tone in itertools.combinations(duration_tones, i):
                accumulate_time = 0
                for index, tuple in enumerate(duration_tone):
                    accumulate_time += tuple[1]
                    if index >= 1:
                        accumulate_time += duration_tone[index][0] - duration_tone[index-1][0]
                if accumulate_time <= T:
                    n = i
                    break
            else:
                break

        return n