Actually, I unfortunately failed in round1. But I find algorithm hacker cup interesting. I wrote some codes as the solutions for this round. Hope you enjoy it.

Pie Progress

We can see that, if he buy pie number $n$ on one day, then he have to pay another $n^2$ money.

Then according to $\sum (2k + 1) = k^2$, we know that we can sort the every day’s pie price, then add odd number to it.

When buying the pies, since it is pre-sorted by the code, adding odd number in growing order to it does not influence the sequence.

Another point need to remember is that: one can not buy a pie that is preceding his day.

For example: if he is on the first day, then he should only buy pies on the first day, rather than pies on the second day or even later.

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cmath> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<deque> using namespace std; intmain() { // input redirection freopen("pieprogress.in", "r", stdin); freopen("pieprocess_cache.out", "w", stdout); // some testcase number input int testcase; cin >> testcase; for (int tes = 0; tes < testcase; tes++) { // given the days and the pie number every day int days, pies_per_day; cin >> days >> pies_per_day; deque<int> prices[300]; for (int i = 0; i < days; i++) { // take in the money of each pie for (int j = 0; j < pies_per_day; j++) { int temp; cin >> temp; prices[i].push_back(temp); } // sort them sort(prices[i].begin(), prices[i].end()); // then add 1 3 5 7 9... to make n^2 for (int j = 0; j < pies_per_day; j++) prices[i][j] += (2 * j + 1); } // total result longlong total_price = 0; for (int i = 0; i < days; i++) { // find the min price // if it is the current min and in the current day // add to total price and pop out int min_price = 0; while (prices[min_price].empty()) min_price++; for (int j = 0; j <= i; j++) if (!prices[j].empty()) if (prices[min_price][0] > prices[j][0]) min_price = j; total_price += prices[min_price][0]; prices[min_price].pop_front(); } cout << "Case #" << tes + 1 << ": " << total_price << endl; } return0; }