# BUILDB - Editorial

Author: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi

Cakewalk

None

# PROBLEM:

Chef does N exercises at times A_1,A_2,…,A_N (in minutes, all distinct) and each exercise provides a tension of B_1,B_2,…,B_N units. In the period between 2 consecutive exercises, his muscles relax R units of tension per minute such that the total tension is nonnegative. Considering the time of exercise and hence tension to be negligible, find the maximum tension he will be feeling in his muscles during the entire period of his workout.

# EXPLANATION:

We only need to find the maximum tension Chef will be feeling in his muscle at any point of his workout. It is quite too easy to notice that the tension starts increasing only and only when Chef starts doing exercise and hence the maximum tension will occur at some index i when he just finished his exercise i.

During two consecutive exercise, Chef’s muscles relax R units of tension per minute such that the total tension is nonnegative. Suppose Chef’s tension is e units after completing (i-1)^{th} exercise. Now, we can find the time for which he relaxes after completing (i-1)^{th} exercise. i.e. t=A[i]-A[i-1]. Hence he can relax min(R*t,e) units of tension during the period between i-1 and i^{th} exercise.

As the maximum tension occurs, as soon as he finishes his exercise. So after completing any exercise i, we check that whether the tension in his body is greater than the maximum tension found so far. If it is so then we will update the maximum tension. Finally, after finishing all the exercises we will output the maximum tension found so far.

# TIME COMPLEXITY:

O(N) per test case

# SOLUTIONS:

Setter
``````#include<bits/stdc++.h>

#define pb push_back
#define ll long long int

using namespace std;

const int maxtest = 10;
const int maxn = 5e4;
const int maxr = 1e5;
const int maxten = 1e5;
const int maxtm = 1e9;

int main()
{
int t; cin >> t;
int n, r;
while(t--){
cin >> n >> r;
vector<int> tm, ten;
int x;
for(int i = 0; i < n; i++){
cin >> x;
tm.pb(x);
}
for(int i = 0; i < n; i++){
cin >> x;
ten.pb(x);
}

ll val = ten[0], ans = val;
for(int i = 1; i < n; i++){
val -= (ll)r * (tm[i] - tm[i - 1]);
val = max(val, (ll)0);
val += ten[i];
ans = max(ans, val);
}
cout << ans << endl;
}
}
``````
Tester
``````
#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
int n;
ll r;
cin >> n >> r;
vector<ll> a(n + 1);
rep(i, 1, n + 1) cin >> a[i];
ll x = 0, ans = 0;
rep(i, 1, n + 1) {
ll b;
cin >> b;
x = max(0LL, x - r * (a[i] - a[i - 1]));
x += b;
ans = max(ans, x);
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
``````
Editorilaist
``````#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
int n,r;
cin>>n>>r;

int a[n],b[n];

for(int i=0;i<n;i++)
cin>>a[i];

for(int i=0;i<n;i++)
cin>>b[i];

int ans=b[0];

int max_ans=b[0];

for(int i=1;i<n;i++){
int temp=a[i]-a[i-1];
ans=max(0ll,ans-temp*r);
ans+=b[i];
max_ans=max(max_ans,ans);
}

cout<<max_ans<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}

``````
7 Likes

#include
using namespace std;
#define ll long long
int main(){
int tc;
cin>>tc;
while(tc–){
ll n,r;//r is relax per minute,and n is count of minutes.
cin>>n>>r;
ll A[n];//array representing time
for(ll i=1;i<=n;i++){
cin>>A[i];
}
ll B[n];//array representing tension at any time
for(ll i=1;i<=n;i++){
cin>>B[i];
}
ll tension[n],max=0;//we define array tension that depicts tension at every A[i].
if(n==1){
max=B[1];
}
else{tension[1]=B[1];
for(ll i=2;i<=n;i++){
tension[i]=tension[i-1]-((A[i]-A[i-1])*r)+B[i];//tension at any point is tensionat previous point minus relax tension and add tension given at that moment i.e B[i]
if(tension[i]>=max){// i am finding out the max element among tension array and that would be our answer
max=tension[i];
}}}
cout<<max<<endl;

``````}
``````

}
plz tell me why compiler is giving wrong answer instead of passing examples succesfully

1)Error in first line
2)while(tc–) in 7th line
3)For each array, while input loop should run from 0 to n-1, you are running it from 1 to n.

https://www.codechef.com/viewsolution/45234336
anyone helpme with the test cases my code fails

you are not correcting tension to zero in case it gets negative. This will affect later maximums.

ok thanks

I cant figure out whats wrong with my solution though
https://www.codechef.com/viewsolution/45192146

can anyone tell me what is wrong with this.

``````
void Solve(){
int n,x;
cin>>n>>x;
ll a[n],b[n];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
ll max_t =0, curr_t=0;
for(int i=0;i<n;i++){
curr_t += b[i];
if(i!=n-1){
curr_t = max(0LL,curr_t-((a[i+1]-a[i])*x));
}
max_t = max(max_t,max(0LL,curr_t));
}
cout<<max_t<<'\n';
}

``````

I think max_t should be placed above the if statement because if we place below the if statement then we wont consider the case for the first time when he is doing the exercise. Hope you understood it.

Wow i feel so dumb. thanks i got this

1 Like

https://www.codechef.com/viewsolution/45236154

What is the problem with my code ? I tried it with the changes suggested in the video for this question but I am still getting an error.

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

``````int t;
cin >> t;
while (t--)
{
ll int N, relief;
cin >> N >> relief;

vector<ll int> times(N);
for (ll int i = 0; i < N; i++)
cin >> times[i];

vector<ll int> tension(N);
for (ll int i = 0; i < N; i++)
cin >> tension[i];

if (N == 1)
{
cout << tension[0] << endl;
}
else
{
ll int T = tension[0];
for (ll int i = 1; i < N; i++)
{
T = T - relief + tension[i];
}
cout << T << endl;
}
}

return 0;
``````

}

can someone tell me what is wrong in my code.

``````#include<bits/stdc++.h>
``````

int main()
{
int test;
std::cin>>test;
while(test–){

``````    int  n,r;
std::cin>>n;
std::cin>>r;
int a[n];
int b[n];

for(int  i =0;i<n;++i){
std::cin>>a[i];
}

for(int  i =0;i<n;++i){
std::cin>>b[i];
}
std::vector<int>vec;
int  m[n-1];
for(int  j =1;j<n;++j){
m[j-1]=a[j]-a[j-1];
}
int  x=0;
for(int  i =0;i<n-1;++i){
x=x+b[i];
vec.push_back(x);
if(x>(r*m[i])){
x=x-(r*m[i]);
}
else{
x=0;
}

}
x+=b[n-1];
vec.push_back(x);
std::sort(vec.rbegin(),vec.rend());
std::cout<<vec[0]<<std::endl;
}

return 0;
``````

}

What is wrong with my code?

using namespace std;

int main() {
int j,t,n,x;
cin>>t;
int c[t];

for(int i=0;i<t;i++)
{
cin>>n>>x;
int ten=0,a[n],b[n];
for(j=0;j<n;j++)
cin>>a[j];
for(j=0;j<n;j++)
{
cin>>b[j];
ten=b[j]+ten;
}
c[i]=ten-((n-1)*x);
}
for(j=0;j<t;j++)
cout<<c[j]<<endl;

return 0;
}

//why isn’t this right?

plz help to figure out error in my code plz

``````#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
wihle(t--)
{
int n,min,i,gap,sum=0,l;
cin>>n>>min;
long int a[n],b[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
cin>>b[i];
}
for(i=0;i<n;i++)
{
gap=a[i+1]-a[i];
sum=sum+b[i]-(gap*min);
}
l=sum+b[n-1];
cout<<l<<"\n";
}
}
``````

#include <bits/stdc++.h>
using namespace std;
int main()
{

``````int t;
cin>>t;

while(t--)
{

long n,r;
cin>>n>>r;
long a[n],b[n];

for(long i=0; i<n; i++)
{
cin>>a[i];
}

for(long i=0; i<n; i++)
{
cin>>b[i];
}

long ans=b[0];

for(long i=1; i<n; i++)
{
ans += b[i] - (a[i] - a[i-1])*r;
if(ans < 0)
ans=0;
}

cout<<ans<<endl;

}

return 0;
``````

}

Can anyone tell me where my code is going wrong. It is giving correct output to the test cases but still, I am getting WA on submission.

please tell me what is wrong with this?

``````#include<bits/stdc++.h>

using namespace std;

long long int max(long long int a,long long int b)
{
if(a>=b)
return a;
else
return b;
}
int main()
{
int i,t;
cin>>t;
for(i=0;i<t;i++)
{
long long q=0;
long n,j,r,k;
cin>>n>>r;
vector<long long> a(n), b(n),ans(n);
for(j=0;j<n;j++)
{
cin>>a[j];
}
for(j=0;j<n;j++)
{
cin>>b[j];
}
for(j=0;j<n;j++)
{
k=(a[j+1]-a[j])*r;
q+=b[j]-max(k,0);
ans[j]=q;
}
sort(ans.begin(),ans.end());
cout<<ans[n-1];
q=0;
cout<<'\n';
}
return 0;
}
``````

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()

{

``````int t;

cin >> t;

while (t--)

{

ll n, r;

cin >> n >> r;

ll a[n];

ll b[n];

for (ll i = 0; i < n; i++)

{

cin >> a[i];

}

for (ll i = 0; i < n; i++)

{

cin >> b[i];

}

ll tension = 0;

for (ll i = 0; i < n; i++)

{

tension = tension + b[i];

}

ll rest = 0;

for (ll i = 1; i < n; i++)

{

rest = rest + r * (a[i] - a[i - 1]);

}

ll final_tension = 0;

final_tension = tension - rest;

if (final_tension < 0)

cout << 0 << endl;

else

cout << final_tension << endl;

}

return 0;
``````

}

MAY I KNOW WHAT IS WRONG IN THIS CODE

#include
using namespace std;
int main()
{ int t;
cin>>t;
while(t>0)
{
long long int n,r,i,x=0,y=0,ans;
cin>>n>>r;
long long int a[n],b[n];
for(i=1;i<=n;i++)
{
cin>>a[i];
}
for(i=1;i<=n;i++)
{
cin>>b[i];
}

``````for(i=1;i<=n;i++)
{
x=x+b[i];
}
for(i=1;i<n;i++)
{
y=y+((a[i+1]-a[i])*r);
}
ans=x-y;
cout<<ans<<endl;
t--;
}
``````

}

SOMEONE PLS TELL MY MISTAKE !

while (t–)
{
ll int N, relief;
cin >> N >> relief;

``````vector<ll int> times(N);
for (ll int i = 0; i < N; i++)
cin >> times[i];

vector<ll int> tension(N);
for (ll int i = 0; i < N; i++)
cin >> tension[i];

if (N == 1)
{
cout << tension[0] << endl;
}
else
{
ll int T = tension[0];
for (ll int i = 1; i < N; i++)
{
// You are calculating tension -> by including subtraction of relief and
// addition of tension in next exercise which is wrong.

T = T - relief + tension[i];

// Instead of this as mentioned in the Q that before any workouts, relief =0.
// so in above statement if (T  -  relief ) < 0 then T should be considered as
// zero before adding another exercise tension to it.
// and relief  is not alone to be considered as relief it must be ->
//  relief (times[i]  - times[i-1])
/*  T = T - relief (times[i] - times[i-1]) ;
if(T < 0)
T = 0;
T = T + tension[i];   */
}
cout << T << endl;
}``````
2 Likes