Decidophobia

The trap is thinking this is a complicated subset problem on a circular graph. It looks like the choices should interact. They do not. The algebra nukes the interaction completely.

Let

$$s_i=\begin{cases} 1 & \text{if person } i \text{ receives a gift},\\ -1 & \text{otherwise}. \end{cases}$$

For one ordered visible relation $(i,j)$, person $i$'s contribution caused by person $j$ is:

$$\frac{a_i(s_i-s_j)}{2}.$$

Check it directly:

• same decision: $s_i-s_j=0$, contribution $0$;
• $i$ gifted and $j$ not gifted: contribution $a_i$;
• $i$ not gifted and $j$ gifted: contribution $-a_i$.

So the total happiness is

$$H=\frac12\sum_i\sum_{j\in N(i)} a_i(s_i-s_j),$$

where $N(i)$ is the field of view of person $i$.

Split the sum:

$$H=\frac12\sum_i s_i\cdot 2d a_i -\frac12\sum_i\sum_{j\in N(i)} a_i s_j.$$

The visibility relation is symmetric: if $j$ is in $i$'s field of view, then $i$ is in $j$'s field of view. Therefore, in the second double sum, we can collect terms by $s_i$ instead:

$$H=\frac12\sum_i s_i\left(2d a_i-\sum_{j\in N(i)}a_j\right).$$

Define

$$C_i=2d a_i-\sum_{j\in N(i)}a_j.$$

Then

$$H=\frac12\sum_i s_i C_i.$$

This is the whole problem. There is no DP, no sorting, no spooky global constraint. Each $s_i$ is independent now. To maximize $s_iC_i$, choose:

• $s_i=1$ if $C_i>0$;
• $s_i=-1$ if $C_i<0$;
• either choice if $C_i=0$.

Thus the answer is

$$\frac12\sum_{i=1}^n |C_i|.$$

This is always an integer. Every visible unordered pair contributes opposite differences into the coefficient sum, so $\sum_i C_i=0$; the positive and negative parts balance.

Now we only need to compute every field-of-view sum quickly.

Use 1-indexing and build prefix sums over three copies of the circular array. For original person $i$, place them at position

$$p=n+i$$

in the middle copy. Then their counter-clockwise side is

$$[p-d,\ p-1],$$

and their clockwise side is

$$[p+1,\ p+d].$$

So:

$$\text{viewSum}_i=(pref[p-1]-pref[p-d-1])+(pref[p+d]-pref[p]).$$

Then compute $C_i=2d a_i-\text{viewSum}_i$ and add $|C_i|$.

The condition $d<\frac n2$ guarantees the clockwise and counter-clockwise people are distinct, so this matches the statement cleanly.

Complexity per test case is $O(n)$ time and $O(n)$ memory. Use long long, because values can reach about $O(nd\cdot 10^8)$, which is way past int.