Walktober Solution Round G 2022 - Kick Start 2022

Walktober Solution (4pts, 6pts)

Problem

John participates in an annual walking competition called Walktober. The competition runs for a total of N$N$ days and tracks the daily steps of the participants for all the N$N$ days. Each participant will be assigned a unique ID ranging from 1$1$ to M$M$ where M$M$ is the total number of registered participants. A global scoreboard is maintained tracking the daily steps of each participant.

John is determined to win Walktober this year and his goal is to score the maximum daily steps on each of the N$N$ days among all the participants. Having participated in Walktober last year as well, he wanted to know how many steps he fell short of in achieving his goal. Given the previous year scoreboard, calculate the minimum additional steps he needed over his last year score in order to achieve his goal of scoring the maximum daily steps every day.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
The first line of each test case contains three integers M$M$, N$N$, and P$P$ denoting the total number of participants, the total number of days the competition runs, and the last year participant ID of John.
The next M$M$ lines describe the scoreboard of the previous year and contains N$N$ integers each. The j$j$-th integer of the i$i$-th line denotes the step count Si,j${\mathbf{S}}_{\mathbf{i}\mathbf{,}\mathbf{j}}$ of the participant with ID i$i$ on the j$j$-th day of the competition.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the minimum total additional steps needed by John to achieve his goal.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤N≤31$1\le \mathbf{N}\le 31$.
1≤Si,j≤60000$1\le {\mathbf{S}}_{\mathbf{i}\mathbf{,}\mathbf{j}}\le 60000$ for all i$i$ and j$j$.
1≤P≤M$1\le \mathbf{P}\le \mathbf{M}$.

Test Set 1

Time limit: 20 seconds.
M=2$\mathbf{M}=2$.

Test Set 2

Time limit: 40 seconds.
2≤M≤1000$2\le \mathbf{M}\le 1000$.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input

1
2 3 1
1000 2000 3000
1500 1500 3000

Sample Output

Case #1: 500

In the Sample Case, the competition ran for 3$3$ days and the participant ID of John was 1$1$. On day 1$1$, as the other participant has more steps, John needs 500$500$ additional steps. On the rest of the days, as John already has the maximum steps, he needs no additional steps. So, he needs a total of 500$500$ additional steps to achieve his goal.

Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input

save_alt

content_copy

2
3 2 3
1000 2000
1500 4000
500 4000
3 3 2
1000 2000 1000
1500 2000 1000
500 4000 1500

Sample Output

save_alt

content_copy

Case #1: 1000
Case #2: 2500

In the Sample Case #1, the competition ran for 2$2$ days and the participant ID of John was 3$3$. He needs an additional 1000$1000$ steps on day 1$1$ and 0$0$ steps on day 2$2$ to achieve his goal. So, he needs a total of 1000$1000$ additional steps to achieve his goal.

In the Sample Case #2, the competition ran for 3$3$ days and the participant ID of John was 2$2$. He needs an additional 0$0$ steps on day 1$1$, 2000$2000$ steps on day 2$2$, and 500$500$ steps on day 3$3$ to achieve his goal. So, he needs a total of 2500$2500$ additional steps to achieve his goal.

Solution : 

We will maintain the maximum number of steps taken every day by any participant and then calculate the steps needed by John and add it to our answer.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void solve(int tc) {

int m,n,p;

cin>>m>>n>>p;

vector<vi>v(m,vi(n));

vi pre(n,0);

for (int i = 0; i < m; i++)

{

    for (int j = 0; j < n; j++)

    {

        cin>>v[i][j];

        pre[j]=max(pre[j],v[i][j]);

    }

}

int ans=0;

for(int i=0; i<n; i++)ans+=max(0LL,pre[i]-v[p-1][i]);

cout<<"Case #"<<tc<<": "<<ans<<endl;

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

  cin >> t; 

  int k=1;

  while (t--) solve(k++);

  return 0;

}