Official Analysis

Explanation

The key to solving this problem is understanding how to smooth out the salt distribution step by step.

Think of it this way:

1. Moving forward (left-to-right), no slice has too little salt compared to the one before it. Specifically, each slice should have at least as much salt as the previous slice minus $m$. This prevents sharp drops in flavor.
2. Moving backward (right-to-left), no slice has too much salt compared to the next one. Each slice shouldn't exceed the salt level of the next slice plus $m$. This avoids sudden spikes when looking backward.

To achieve this, we break the problem into two steps:

• First, we move left-to-right, ensuring each slice meets the minimum requirement based on the slice before it. This step focuses on preventing bland spots.
• Then, we move right-to-left, smoothing out any excess salt to ensure no slice feels overly salty compared to the next. This step refines the distribution for balance.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <iostream>
#include <vector>

using std::cout;
using std::vector;

int main() {
	int n, m;
	std::cin >> n >> m;
	vector<int> arr(n);

Copy
import java.io.*;
import java.util.*;

public class NusretGokce {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

Copy
n, m = map(int, input().split())
arr = list(map(int, input().split()))

running_max = 0
for i in range(n):
	running_max = max(arr[i], running_max - m)
	arr[i] = running_max

running_max = 0
for i in reversed(range(n)):
	running_max = max(arr[i], running_max - m)
	arr[i] = running_max

print(*arr)