fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.     int T;
  10.     cin >> T;
  11.  
  12.     for (int test_case = 1; test_case <= T; test_case++)
  13.     {
  14.         int n, m;
  15.         cin >> n >> m;
  16.  
  17.         vector<vector<int>> cost(n, vector<int>(m));
  18.         for (int r = 0; r < n; r++)
  19.             for (int c = 0; c < m; c++)
  20.                 cin >> cost[r][c];
  21.  
  22.         for (int r = 0; r < n; r++) sort(cost[r].begin(), cost[r].end());
  23.  
  24.         priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  25.         for (int r = 0; r < n; r++)
  26.             for (int c = 0; c < m; c++)
  27.             {
  28.                 int tax_increase = (c + 1) * (c + 1) - c * c;
  29.                 int real_cost = cost[r][c] + tax_increase;
  30.  
  31.                 pq.push({ real_cost, r });
  32.             }
  33.  
  34.         int cnt = 0;
  35.         int min_cost[300] = {};
  36.         while (cnt < n)
  37.         {
  38.             auto record = pq.top();
  39.             pq.pop();
  40.  
  41.             int r = record.second;
  42.             while (r < n && min_cost[r]) r++;
  43.  
  44.             if (r < n)
  45.             {
  46.                 cnt++;
  47.                 min_cost[r] = record.first;
  48.             }
  49.         }
  50.  
  51.         int sum = 0;
  52.         for (int day = 0; day < n; day++)
  53.             sum += min_cost[day];
  54.  
  55.         cout << "Case #" << test_case << ": " << sum << '\n';
  56.     }
  57. }
Runtime error #stdin #stdout 0.24s 121280KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QakYqG
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!