Submission #1181765

#TimeUsernameProblemLanguageResultExecution timeMemory
1181765mehmetkaganSolar Storm (NOI20_solarstorm)Pypy 3
0 / 100
2095 ms309224 KiB
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...