Submission #1181797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181797		kemalmete1	Solar Storm (NOI20_solarstorm)	Pypy 3	0 / 100	2103 ms	327104 KiB

SolarStorm

temp = [int(v) for v in input().split()]
N = temp[0]
S = temp[1]
K = temp[2]
distances = [int(v) for v in input().split()]
values = [int(v) for v in input().split()]

positions = [0 for _ in range(N)]
curr_sum = 0
for i in range(1, N):
    curr_sum += distances[i-1]
    positions[i] = curr_sum


def is_protected(module, shields):
    protections = [(positions[s] - K, positions[s] + K) for s in shields]
    position = positions[module]
    protected = False
    for lower, upper in protections:
        if lower <= position <= upper:
            protected = True
            break
    return protected


def get_protected_map(shields):
    return [int(is_protected(module, shields)) for module in range(N)]


def fitness(shields):
    protected_map = get_protected_map(shields)
    max_values = 0
    curr_values = 0
    for i, p in enumerate(protected_map):
        if p == 1:
            curr_values += values[i]
            max_values = max(curr_values, max_values)
        else:
            curr_values = 0
    return max_values


shield_maps = 2**N
best_fitness = 0
best_shields = []
for shield_map in range(shield_maps):
    shields = [i for i in range(N) if (shield_map >> i) & 1 == 0]
    if len(shields) > S:
        continue
    curr_fitness = fitness(shields)
    if curr_fitness > best_fitness:
        best_fitness = curr_fitness
        best_shields = shields
    elif curr_fitness == best_fitness and len(shields) < len(best_shields):
        best_shields = shields

print(len(best_shields))
print(" ".join([str(s+1) for s in best_shields]))

Compilation message (stdout)

Compiling 'SolarStorm.py'...

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

=======

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