Problem: pieprogress (2017 round1)

Some pies are sweet, full of fruit and jam and sugar.

Some pies are savory, full of meat and potatoes and spices.

Some pies are in fact not pies at all but tarts or galettes. This probably
won't stop you from eating them.

Every single day for **N** days, you're determined to eat a pie for dinner.
Every morning, you'll take a trip to your local pie shop, and buy 0 or more of
their pies. Every night, you'll eat one pie that you've bought. Pies never go
bad, so you don't need to eat a pie on the same day that you bought it. You
may instead eat one that you purchased on an earlier day.

On the _i_th day, the shop has **M** pies for sale, with the _j_th of these
pies costing **Ci,j** dollars. You can choose to buy any (possibly empty)
subset of them. However, this shop has measures in place to protect itself
against crazy pie fanatics buying out its products too quickly. In particular,
if you buy **p** pies on a single day, you must pay an additional tax of
**p**2 dollars.

### Input

Input begins with an integer **T**, the number of times you go on a pie-eating
spree. For each case, there is first a line containing two space-separated
integers, **N** and **M**. Then, **N** lines follow, each containing **M**
space-separated integers. The _j_th integer on the _i_th line is **Ci,j**.

### Output

For the _i_th case, print a line containing "Case #**i**: " followed by the
minimum you need to pay to eat a pie every day.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **N**, **M** ≤ 300  
1 ≤ **Ci,j** ≤ 1,000,000  

### Explanation of Sample

In the first case, you should buy both pies on the first day, for a total cost
of 1 + 1 + 22 = 6. On the second day you should buy one pie for 100 + 12 =
101. On the third day you can eat one of the spare pies you bought on the
first day.

In the third case, you should buy and eat the cheapest pie every day, for a
daily cost of 1 + 12 = 2, and a total cost of 10.

In the fourth case, one possible solution is to buy two pies on the first day
(1 + 1 + 22 = 6), two pies on the second day (2 + 2 + 22 = 8), and one pie on
the third day (3 + 12 = 4) for a total cost of 18. On the fourth and fifth
days you can eat your two spare pies from the first and second days.



Sample input:
5
3 2
1 1
100 100
10000 10000
5 1
1
2
3
4
5
5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
5 5
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
10 4
7 15 12 6
15 3 19 18
10 9 10 14
12 14 8 8
5 3 5 11
9 14 19 11
12 6 20 9
18 13 12 15
14 14 10 20
11 19 12 11


Sample output:
Case #1: 107
Case #2: 20
Case #3: 10
Case #4: 18
Case #5: 79



Code: // Hacker Cup 2017
// Round 1
// Pie Progress
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
	int T,t;
	int N,M;
	int i,ans;
	int C[300];
	priority_queue<int> Q;
	Read(T);
		Fox1(t,T)
		{
			Read(N),Read(M);
			ans=0;
				while (N--)
				{
						Fox(i,M)
							Read(C[i]);
					sort(C,C+M);
						Fox(i,M)
							Q.push(-(C[i]+Sqr(i+1)-Sqr(i)));
					ans-=Q.top(),Q.pop();
				}
				while (!Q.empty())
					Q.pop();
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}