Submission #1181765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181765		mehmetkagan	Solar Storm (NOI20_solarstorm)	Pypy 3	0 / 100	2095 ms	309224 KiB

SolarStorm

import sys
import math

def main():
    N, S, K = map(int, sys.stdin.readline().split())
    d = list(map(int, sys.stdin.readline().split()))
    v = list(map(int, sys.stdin.readline().split()))
    
    x = [0] * (N + 2)
    for i in range(2, N + 1):
        x[i] = x[i - 1] + d[i - 2]
    
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i - 1] + v[i - 1]
    
    end_idx = [0] * (N + 1)
    j = 1
    for i in range(1, N + 1):
        while j <= N and x[j] <= x[i] + K:
            j += 1
        end_idx[i] = j - 1
    
    log_max = 20
    up = [[0] * (N + 2) for _ in range(log_max)]
    up[0] = end_idx
    
    for k in range(1, log_max):
        for i in range(1, N + 1):
            up[k][i] = up[k - 1][up[k - 1][i] + 1] if (up[k - 1][i] + 1 <= N) else up[k - 1][i]
    
    def compute_shields(L, R):
        pos = L
        count = 0
        for k in reversed(range(log_max)):
            if pos > R or count >= S:
                continue
            next_pos = up[k][pos]
            if next_pos > R:
                continue
            count += (1 << k)
            pos = next_pos + 1
        for k in range(10):
            if pos > R or count >= S:
                break
            if end_idx[pos] >= R:
                count += 1
                break
        
        if pos <= R:
            count = S + 2
        return count

    best_sum = -1
    best_l = 1
    best_r = 1

    for L in range(1, N + 1):
        R = L
        current_sum = prefix_sum[R] - prefix_sum[L - 1]
        if current_sum > best_sum:
            best_sum = current_sum
            best_l = L
            best_r = R
        
        j = end_idx[L]
        R_current = L
        while R_current <= N and compute_shields(L, R_current) <= S:
            R_current = end_idx[R_current]
            R_current = (min(R_current, N))
        R_max = R_current
        R_current = L
        while R_current <= N and R_current <= R_max:
            current_sum = prefix_sum[R_current] - prefix_sum[L - 1]
            if current_sum > best_sum:
                best_sum = current_sum
                best_l = L
                best_r = R_current
            R_current += 1

    shield_positions = []
    pos = best_l
    while pos <= best_r and len(shield_positions) < S:
        current_end = end_idx[pos]
        shield_positions.append(current_end)
        pos = current_end + 1

    print(len(shield_positions))
    print(' '.join(map(str, shield_positions)))

if __name__ == '__main__':
    main()

Compilation message (stdout)

Compiling 'SolarStorm.py'...

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

=======

• 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