PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Cakewalk
PREREQUISITES:
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;
}
