First i calculated ans by taking service for each day(c[i])

then i calculated for how many days i will be paying x amount of cost using prefix sum technique(Prefix sum using maps).

Then working smartly i store cost for day intervals(like x to y) in a data structure.

Then simply calculated if using C yen from day x to day y is useful or not.

for better understanding see this code below https://atcoder.jp/contests/abc188/submissions/19339488

To solve D, I use Sweep-Line algorithm

for D I use coordinate compression,

D seems pretty standard iteration over all discrete point boundaries and since for each range the minimum answer is the same for each day, we can add its range * minimum answer for the range to the final answer.

For F, I came up with this solution : Decide how many multiplication operations one will use (iterate on it, because it's max around log2(y/x) +- 2, say 'i' is the pointer). Now if we use these many multiplications, subtract contribution of original value * 2^(i) from the final required value. Now take the absolute value of the difference. We now need to arrange subtraction and addition operations in the original multiplication operations so as to make difference = 0 while minimizing total operations. Here we an observe that if we move optimally, there are at max 2*i + 1 distinct values that will be assumed by the difference if we start reducing from the highest bit. You can understand it like this : We either just reach the particular value or just exceed it using our difference operations at every bit. It doesn't make sense to go too far from the given difference. We can find these by taking modulo of difference, say m, with (2^j) making m and (2^j) — m as the optimal values for all j from 0 to i. Now we can run a dynamic programming from these values to get the minimum answer for i as dp[difference] + i. Minimum over all i is the required answer.

Push the start/end of each service into a priority queue sorted by day, go from lowest to highest, keep track of current sum of separate fees and you can calculate Ans += min(sum, prime fee) * elapsed days

Put beginnings and ends into one array and sort by their time (keep track to which interval they belong to and whether they are start/end of the interval). Then scan along this array and compute the current price for one day. This price holds for the whole interval from the current processed event (beginning/end of interval) to the previous event. Of course, instead of this price, we can choose the price C (the whole subscription). So we add the chosen price multiplied by the time since the last event to the result.

Solution to F was already there on Stackoverflow.

What is your logic?

Try this one: 1 47. The answer is 7 = (1x2+1)x2x2x2x2-1

I was also getting the same verdict which was due to the integer overflow. Try to look for that.

Your DFS doesn't seem to be working in linear time. For example, consider

1 2
1 3
2 3

Let's say your DFS starts from 1, then visits 3. Then it will backtrack to 1, and visit 2. Then your DFS again visits 3, even though it is already visited. So this can time out for large graphs.

Try to solve with Dijsktra's Algorithm. There are better solutions but using Dijkstra works for this

long a=pc*d;

long b=k*d;

This line is causing use WA due to interger overflow. Try to do —

long val = min(pc, k) * d;

One possible bug is if you include node into its subtree, but Example #3 should rule this out. Also if you use dfs for a subtree max and don't use dp then you get quadratic solutions which TLEs. Other possible bugs include wrong initialization of dp (for example, initializing best answer to 0 instead of -inf or initializing subtree max to something nonzero).

If by sub-tree you mean all nodes reachable from current node , then your logic is correct , there must be coding mistake . Usually sub-tree word we use in case of tree but that was not the input .

You need to reverse the edges to calculate values starting from the selling point (largest numbers)

If you do it your way, you can loose some values on the way

say roads are 1->3->5 and 2->3->6

If you start from 1, you will update values for 3 and 5 from 1, values from 2 will never reach 6 because 3 is already visited

If i am not wrong , your submission is failing on (input format same as question) :

3 3 2 1 100 1 3 2 3 1 2

Answer is 99 , yours give 98 .

Because in your DFS solution , vertex 3rd is not taken into account when you are at vertex 2nd .

Ah, ok, found the problem.

"buy 1 kilogram of gold at some town, traverse one or more roads, and sell 1 kilogram of gold at another town."

So, like the examples say, the result can be negative. I did not consider that.

We bought the gold from city say (i), now we don't sell at the same city, that's why we will be looking at the child of current city for selling.

ckmax(maksi[s], a[s]);

You assume that you can sell at the same city as you bought, but that is not the case, you can only sell in another city.

Please ignore.. will ask here https://codeforces.net/blog/entry/86642

You are not updating the mi[] correctly:

The first and/or last intervals are not calculated proper. Consider the first interval starts at day 10. Then you add 10*something to the solution, what is not correct.