Sorry, I had messed up the transitions. They're correct now. Thanks for the feedback :D

Another way to think about the solution for B is:

Let $$$pos[i]$$$ be the count of sub arrays that end in i ($$$[k..i]$$$ for $$$k \geq 0$$$) whose product is positive, and $$$neg[i]$$$ the count of subarrays that end in i ($$$[k..i]$$$ for $$$k \gt = 0$$$) whose product is negative.

The base case for them is simple:

pos[0] = 1 if v[0] > 0, otherwise 0
neg[0] = 1 if v[0] < 0, otherwise 0

Given that $$$pos[x-1]$$$ and $$$neg[x-1]$$$ are calculated, we can easily calculate $$$pos[x]$$$ and $$$neg[x]$$$ as follows:

pos[x] = 1+pos[x-1] if v[x] > 0,
pos[x] = neg[x-1] if v[x] < 0

neg[x] = neg[x-1] if v[x] > 0,
neg[x] = 1+pos[x-1] if v[x] < 0

After these arrays are fully calculated, the amount of sub arrays that are positive is the sum of all $$$pos[i]$$$, and the amount of arrays that are negative is the sum of $$$neg[i]$$$

My submission 60721761

run dijkstra from vertex 1 to all other ones

that gives you a tree of shortest paths

all you need to do is remove leaf by leaf untill you have k+1 vertices (and k edges)

it clearly maximizes the number of 'good vertices' and is always valid as well

why exactly did people try to submit solutions with cout << 0 anyway?

that feels just odd to me

45341495

my solution for D is WA on #7, can someone tell me what i'm doing wrong?

i'm counting for every 'i' the size of the largest array [i, i+1, ...] that is present on every array, then i sum all these values. my code returns correct results for all other testcases with small size

Nice, really clean solution. Thanks a lot for the explanation :D