# Lectures At School DSA Problem Solution

In this post, we are going to solve Lectures At School DSA Problem from Standard Chartered, On-Campus Questions. Let’s have a look at the problem statement first and then try to solve the problem.

## Lectures At School DSA Problem Statement

A student in Hacker School is provided with an

$n$$n$ days schedule in which each day, up to

$m$$m$ hours of lecture classes take place.

The schedule of the school is given by a binary matrix

$schedule\left[\right]\left[\right]$$schedule[][]$ where

$scheduled\left[i\right]\left[j\right]=1$$scheduled[i][j]= 1$ denotes that there is a lecture on the

${j}_{th}$$j_{th}$ hour of the

${i}_{th}$$i_{th}$ day and

$schedule\left[i\right]\left[j\right]=0$$schedule[i][j] = 0$ denotes that there is no lecture on the

${j}_{th}$$j_{th}$ hour of the

${i}_{th}$$i_{th}$ day.

In a single day, if the student attends the first lecture at the

${x}_{th}$$x_{th}$ hour and the last lecture at the

${y}_{th}$$y_{th}$ hour, then it takes them

$\left(y-x+1\right)$$(y-x+1)$ hours of time to attend school on that day. The student is allowed to skip at most

$k$$k$ lectures in total for all the

$n$$n$-days. Find the minimum total amount of time (in hours) the student needs to attend school, including all the

$n$$n$ days if the lectures to be skipped are chosen optimally.

Input

The first line contains 3 space-separated integers in form :

$1\le n\le 200$$1\le n \le 200$

$1\le m\le 200$$1\le m \le 200$

$1\le k\le 200$$1\le k \le 200$.

Then follows

$n$$n$ lines each consisting of binary string of length

$m$$m$ where

${i}_{th}$$i_{th}$ line denotes schedule of

${i}_{th}$$i_{th}$ day.

Output

Output minimum total time required to attend the school.

Example
Input
1 5 1
10001
Output
1

Note

In the given test case:

Consider 1-based indexing and

$n=1$$n=1$

$m=5$$m=5$

$k=1$$k=1$ and schedule of day

$1$$1$ is

$10001$$10001$

The student can skip the last lecture of the first day, that is,

$schedule\left[1\right]\left[5\right]$$schedule[1][5]$. Then, they only have to attend one lecture at the

${1}_{th}$$1_{th}$ hour, so the total time spent at school = 1, which is the minimum possible. Thus, the answer is 1.

## Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int dp[201][201];
int t[201][201];
char s[201][201];

int solve(int day, int skip)
{
if(skip < 0)
return 1e9;

if (day < 0)
return 0;

if (dp[day][skip] != -1)
return dp[day][skip];

int res = INT_MAX;
for (int x = 0; x <= skip; x++)
res = min(res, solve(day - 1, skip - x) + t[day][x]);

return dp[day][skip] = res;
}

void computeTime()
{
for (int i = 0; i < n; i++)
for (int j = 0; j <= k; j++)
t[i][j] = INT_MAX;

for (int i = 0; i < n; i++)
{
vector<int> pos;
for (int j = 0; j < m; j++)
if (s[i][j] == '1')
pos.push_back(j);

int sz = pos.size();

for (int x = 0; x <= k; x++)
{
if (x >= sz)
t[i][x] = 0;
else
{
t[i][x] = pos[sz - 1] - pos[0] + 1;
for (int j = 0; j < sz; j++)
{
int left_remove = j;
if (left_remove > x)
break;
int more = x - left_remove;
int r = sz - 1 - more;
t[i][x] = min(t[i][x], pos[r] - pos[j] + 1);
}
}
}
}
}

int main()
{
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> s[i][j];
memset(dp, -1, sizeof(dp));
computeTime();
cout << solve(n - 1, k);
}