Subtask 1
Observe that the only field positions that can be optimal are between the leftmost and rightmost positions of all friends, so we can simply check those positions.
Time Complexity: 
~\mathcal{O}(N \times \max(P_i))~
Subtask 2
We use the same observation as the last subtask except we must check positions more quickly, which we can do with linesweep.
Consider how the answer changes as we move from position 
~x~ to 
~x+1~: for every 
~i~ where 
~P_i+D_i \le x~, we must add 
~W_i~ to the answer, and for every 
~j~ where 
~x < P_j-D_j~, we must subtract 
~W_j~ from the answer. Thus, we simply need to maintain the sum of weights on the left and right of the current position.
Note: At any position ~x~, let 
~\text{leftSum}=\sum_{i=1,x \ge P_i+D_i}^N W_i~ and 
~\text{rightSum}=\sum_{i=1,x < P_i-D_i}^N W_i~.
This solution can also be used to explain why field positions between the leftmost and rightmost positions of all friends are optimal: if we are to the left of the leftmost position of a friend, 
~\text{leftSum}=0~ while 
~\text{rightSum}>0~, so moving to the right will always result in a better answer. A similar argument can be used to prove the same for positions to the right of the rightmost position of a friend.
Time Complexity: 
~\mathcal{O}(N + \max(P_i))~
Subtask 3
The solution from subtask 
~2~ can be extended by realizing that an optimal answer will be at 
~P_i \pm D_i~ for some 
~1 \le i \le N~ (we'll call these positions candidate positions). We can prove this by considering the 
~\text{leftSum}~ and 
~\text{rightSum}~ variables again: ~\text{leftSum}~ and ~\text{rightSum}~ only change at candidate positions, meaning that if we're between two candidate positions, we can always move left (if 
~\text{leftSum} \le \text{rightSum}~) or right (if 
~\text{leftSum} \ge \text{rightSum}~) until we reach a candidate position for a better answer.
Time Complexity: 
~\mathcal{O}(N \log N)~
Alternative Solution
Let 
~f_i(x)~ be the walking time of the ~i~th friend if the concert was at position ~x~.
$$\displaystyle f_i(x) = \begin{cases}
W_i \times (P_i-D_i-x) & \text{if }x < P_i-D_i \\
0 & \text{if } P_i-D_i \le x \le P_i+D_i \\
W_i \times (x-P_i-D_i) & \text{if }x > P_i+D_i
\end{cases}$$
We can prove that ~f_i(x)~ is convex for all ~1 \le i \le N~ using one of the conditions for convex functions:
A function 
~f~ is convex if for all 
~0 \le t \le 1~ and 
~x_1, x_2 \in X~ (where 
~X~ is the domain of ~f~), 
~f(tx_1+(1-t)x_2) \le tf(x_1)+(1-t)f(x_2)~. Geometrically, this means that if we draw a line between 
~(x,f(x))~ and 
~(y,f(y))~ for any 
~x,y~ in ~f~'s domain, it must sit above the graph of ~f~. A bit of drawing on a sheet of paper and observing how 
~f_i~ looks like a straightened out parabola can help convince us that it satisfies the condition. However, we can also prove this formally by considering the 
~6~ possible cases of which piece of ~f_i~ (~f_i~ is piecewise) 
~x_1~ and 
~x_2~ fall on.
To complete our solution, observe that as the sum of convex functions is also convex, 
~F(x) = f_1(x)+f_2(x)+\dots+f_N(x)~ is convex as well. Thus we can binary search for the first point where 
~F(x)~ changes from decreasing to non-decreasing, which will be our answer.
Evaluating ~f_i(x)~ for any 
~i,x~ takes 
~\mathcal{O}(1)~ time, so evaluating ~F(x)~ takes 
~\mathcal{O}(N)~ time.
Time Complexity: 
~\mathcal{O}(N \log P_i)~
Comments
What data structure would be best to keep track of
, 
, and 
? (C++)
Also is sorting necessary in this problem?
For the second subtask, how do we check if a person is on the left of right of a position
x? Would that require us to iterate over each person every time we move positionx?binary search,
I tried binary search, but I can't get it to work. What am I doing wrong?
I first iterate over each person once to calculate and record the spots that weight changes when passing. Then I just loop through the line while checking the spots. This is enough to get through subtask 2.