fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef pair<int, int> pii;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vll;
  11. typedef string str;
  12.  
  13. #define pb push_back
  14. #define mp make_pair
  15. #define fi first
  16. #define se second
  17. #define all(x) (x).begin(), (x).end()
  18. #define len(x) ((int)(x).size())
  19.  
  20. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  21. #define forr(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
  22. #define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)
  23.  
  24. #define cmin(a, b) a = min(a, b)
  25. #define cmax(a, b) a = max(a, b)
  26.  
  27. const ll INF = 1e18;
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(NULL);
  32.  
  33.     // freopen("CAU4_17.INP", "r", stdin);
  34.     // freopen("CAU4_17.OUT", "w", stdout);
  35.  
  36.     int m, n, d, r;
  37.     ll h;
  38.     if (!(cin >> m >> n >> d >> r >> h)) return 0;
  39.  
  40.     vector<vll> P(m + 1, vll(n + 1, 0));
  41.  
  42.     forr(i, 1, m) {
  43.         forr(j, 1, n) {
  44.             ll val;
  45.             cin >> val;
  46.             ll cost = abs(val - h);
  47.             P[i][j] = cost + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
  48.         }
  49.     }
  50.  
  51.     ll min_cost = INF;
  52.  
  53.     auto get_sum = [&](int x1, int y1, int x2, int y2) {
  54.         return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
  55.     };
  56.  
  57.     if (r <= m && d <= n) {
  58.         forr(i, r, m) {
  59.             forr(j, d, n) {
  60.                 ll current_cost = get_sum(i - r + 1, j - d + 1, i, j);
  61.                 cmin(min_cost, current_cost);
  62.             }
  63.         }
  64.     }
  65.  
  66.     if (d <= m && r <= n) {
  67.         forr(i, d, m) {
  68.             forr(j, r, n) {
  69.                 ll current_cost = get_sum(i - d + 1, j - r + 1, i, j);
  70.                 cmin(min_cost, current_cost);
  71.             }
  72.         }
  73.     }
  74.  
  75.     if (min_cost == INF) {
  76.         cout << -1 << "\n";
  77.     } else {
  78.         cout << min_cost << "\n";
  79.     }
  80.  
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
5 6 
4 2 2 
3 4 2 4 3 3 
4 5 2 2 5 3 
1 4 3 2 5 4 
3 4 2 1 5 3 
3 4 2 3 1 5
stdout
copy 
3
https://ideone.com/zU71Vn
language:
C++14 (clang 8.0)
created:
1 day 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!