fork download
copy 
  1. #include <algorithm>
  2. #include <array>
  3. #include <cassert>
  4. #include <chrono>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <functional>
  8. #include <iomanip>
  9. #include <iostream>
  10. #include <map>
  11. #include <numeric>
  12. #include <queue>
  13. #include <random>
  14. #include <set>
  15. #include <vector>
  16. using namespace std;
  17.  
  18. // http://w...content-available-to-author-only...d.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
  19. template <class Fun>
  20. class y_combinator_result
  21. {
  22.     Fun fun_;
  23.  
  24. public:
  25.     template <class T>
  26.     explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
  27.     template <class... Args>
  28.     decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
  29. };
  30. template <class Fun>
  31. decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
  32.  
  33. template <typename A, typename B>
  34. ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  35. template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
  36. ostream &operator<<(ostream &os, const T_container &v)
  37. {
  38.     os << '{';
  39.     string sep;
  40.     for (const T &x : v)
  41.         os << sep << x, sep = ", ";
  42.     return os << '}';
  43. }
  44.  
  45. void dbg_out() { cerr << endl; }
  46. template <typename Head, typename... Tail>
  47. void dbg_out(Head H, Tail... T)
  48. {
  49.     cerr << ' ' << H;
  50.     dbg_out(T...);
  51. }
  52. #ifdef NEAL_DEBUG
  53. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  54. #else
  55. #define dbg(...)
  56. #endif
  57.  
  58. const int DIRS = 4;
  59. const int DR[DIRS] = {-1, 0, +1, 0};
  60. const int DC[DIRS] = {0, +1, 0, -1};
  61.  
  62. struct state
  63. {
  64.     int height, r, c;
  65.  
  66.     bool operator<(const state &other) const
  67.     {
  68.         return height < other.height;
  69.     }
  70. };
  71.  
  72. void run_case(int test_case)
  73. {
  74.     int R, K;
  75.     cin >> R >> K;
  76.     vector<vector<int>> grid(R, vector<int>(R));
  77.  
  78.     for (auto &row : grid)
  79.         for (auto &x : row)
  80.             cin >> x;
  81.  
  82.     priority_queue<state> pq;
  83.  
  84.     for (int r = 0; r < R; r++)
  85.         for (int c = 0; c < R; c++)
  86.             pq.push(state({grid[r][c], r, c}));
  87.  
  88.     int64_t total = 0;
  89.  
  90.     auto pq_check = [&](int r, int c, int height) {
  91.         if (height > grid[r][c] and  height - grid[r][c]>K)
  92.         {
  93.             total += height - grid[r][c]-K;
  94.             grid[r][c] +=  height - grid[r][c]-K;
  95.             pq.push(state({grid[r][c], r, c}));
  96.         }
  97.     };
  98.  
  99.     while (!pq.empty())
  100.     {
  101.         state top = pq.top();
  102.         pq.pop();
  103.         int r = top.r, c = top.c;
  104.  
  105.         for (int dir = 0; dir < DIRS; dir++)
  106.         {
  107.             int nr = r + DR[dir];
  108.             int nc = c + DC[dir];
  109.  
  110.             if (0 <= nr && nr < R && 0 <= nc && nc < R)
  111.                 pq_check(nr, nc, top.height);
  112.         }
  113.     }
  114.     for(int i=0;i<R;i++){
  115.         for(int j=0;j<R;j++){
  116.             cout<<grid[i][j]<<" ";
  117.         }cout<<'\n';
  118.     }
  119.     cout << "Case #" << test_case << ": " << total << '\n';
  120. }
  121.  
  122. int main()
  123. {
  124.     int tests=1;
  125.     // cin >> tests;
  126.  
  127.     for (int tc = 1; tc <= tests; tc++)
  128.     {
  129.         run_case(tc);
  130.         cout << flush;
  131.     }
  132. }
  133.  
Success #stdin #stdout 0s 5500KB
comments (?)
stdin
copy 
2 4 
1 7
7 13
stdout
copy 
5 9 
9 13 
Case #1: 8
https://ideone.com/QSEdgq
language:
C++ (gcc 8.3)
created:
2 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!