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%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |