 # GCJ Manage Your Energy Problem with pieguy's submission

I was reading the submissions and came along a neat submission by the very own @pieguy (You know him, as he is setter of many problems in the Contests here at Codechef).

I am pasting the code snippets where I have doubt, if anyone or @pieguy himself can explain this, then it will really be helpful.

``````#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int E, R;
long long solve(int* start, int length, int se, int ee) {
if(length == 0)
return 0;
long long pos = max_element(start, start+length) - start;
long long ie = pos*R+se;
if(ie > E)
ie=E;
long long re = ee-(length-pos)*R;
if(re < 0)
re=0;
long long res=(ie-re)*start[pos];
res+=solve(start, pos, se, ie);
res+=solve(start+pos+1, length-pos-1, re+R, ee);
return res;
}

int main(){
int T;
scanf("%d", &T);
for(int t=1; t<=T; t++) {
int N, v;
scanf("%d%d%d", &E, &R, &N);
for(int i=0; i<N; i++)
scanf("%d", v+i);
printf("Case #%d: %lld\n", t, solve(v, N, E, R));
}
}
``````

This was the solve() that he used, the intitial call was made by

``````solve(v, N, E, R)
``````

For meaning of symbols refer to the [problem.]

v is the array to store each vi.

I did not understand the

``````ie = pos*R + se;
``````

part, why is he multiplying regain amount to the position of the max element and then adding to the initial energy.
Again, while calculating re, he is doing something similar.

1 Like

@bugkiller would need a little more code

but here is what i get from this…

he finds the position for the maximum element to make sure he has full E available for that task…
he is multiplying pos*R because he want to know how much energy is available till he reaches that position…

which will be E+pos*R … so pos*R is the energy he can use between 1st and max position task…
(amount of energy, R, the amount you regain after each activity)

1 Like

How is the energy he can use between 1st and max position pos*R? Can you please explain the idea a bit in detail?

Problem statement:
and you get R energy after doing every task…

the best way to maximize gain is to use maximum energy on most important task…

till he reach his most important task he will have R*pos energy from doing pos amount of tasks…
then he divide his problem into two halves
(1,max_pos) && (max_pos+1 N)

and the first half can use R*pos+E amount of energy where pos task will consume E energy

and second half can use R*(N-pos) amount of energy

1 Like

“the first half can use R*pos+E amount of energy where pos task will consume E energy” Is it always possible to spend E amount of energy to the max element? So should I assume that from elements 1 through pos, I am spending R amount of energy always and then spending E on the pos element, right?

yes because you start with E amount of energy so you can have E at any task position if you dont spend on any task