https://www.codechef.com/DCOF2021/problems/K3006

Problem : Find Sequence

Problem link: Contest Page | CodeChef

**Difficulty** : Hard

**Prerequisites** : DP, Greedy, Implementation

**Problem :**

To find time at which each vehicle will be ready for shipment

rules:

1 worker work in a sequence i.e. first the first worker then second and so on.

2 a worker cannot start on a vehicle until his previous work is done and the last worker is finished on the current vehicle.

**Explanation** :

Look at it as a scheduling problem where a task cannot begin until the previous task ends

Thus, an employee can start his work if the previous employee did his work and also he is free to do so

Creating a bottom-up approach for this question is ideal.

make a 2-d array that will store appropriate details about each vehicle and work done on it

Time complexity should be O(n*e) where n is number of vehicle and e is number of employees;

Thank you.

**Solution** :

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
void dev()
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> arr(n, vector<ll>(m));
vector<vector<ll>> brr(n, vector<ll>(m));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
cin >> arr[i][j];
brr[i][j] = 0;
}
}
for (ll i = 0; i < n; i++)
{
if (i == 0)
{
brr[i][0] = arr[0][0];
}
else
{
brr[i][0] = brr[i - 1][0] + arr[i][0];
}
}
for (ll i = 1; i < m; i++)
{
brr[0][i] = brr[0][i - 1] + arr[0][i];
}
for (ll i = 1; i < n; i++)
{
for (ll j = 1; j < m; j++)
{
brr[i][j] = max((brr[i - 1][j] + arr[i][j]), (brr[i][j - 1] + arr[i][j]));
}
}
for (ll i = 0; i < n; i++)
{
cout << brr[i][m - 1] << " ";
}
cout<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
cin >> t;
while (t--)
{
dev();
}
return 0;
}
```

Thank you