SHARE
TWEET

Untitled

a guest Jul 3rd, 2017 123 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <string>
  6. #include <utility>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <set>
  10. #include <map>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. #define FOR(a, b) for (int a = 0; a < b; a++)
  16. #define clr(a) memset(a, 0, sizeof(a))
  17. #define ll long long
  18. //define _in_s(a, b) (((a) < h)&&((a) >= 0)&&((b) < w)&&((b) >= 0))
  19. //const ll INF = (ll)1000000000 * (ll)1000000000;
  20. const int INF = 1000000000;
  21.  
  22.  
  23. struct point{
  24.     short int x, y;
  25. };
  26.  
  27.  
  28. int l, w, n, k;
  29. int m[250][250];
  30. int pr[250][250];
  31. int ml[250];
  32. int mr[250];
  33.  
  34. inline int getS(int x1, int y1, int x2, int y2)
  35. {
  36.     if (y1 == 0 && x1 == 0) return pr[x2][y2];
  37.     if (y1 == 0) return pr[x2][y2] - pr[x1 - 1][y2];
  38.     if (x1 == 0) return pr[x2][y2] - pr[x2][y1 - 1];
  39.     return pr[x2][y2] - pr[x2][y1 - 1] - pr[x1 - 1][y2] + pr[x1 - 1][y1 - 1];
  40. }
  41.  
  42. inline int getP(int x1, int y1, int x2, int y2)
  43. {
  44.     return 2 * (x2 - x1 + y2 - y1 + 2);
  45. }
  46.  
  47. int main()
  48. {
  49.     //freopen("b.in", "r", stdin);
  50.     //freopen("b.out", "w", stdout);
  51.     clr(m);
  52.     scanf("%d%d%d%d", &l, &w, &n, &k);
  53.     FOR(i, n)
  54.     {
  55.         int x, y;
  56.         scanf("%d%d", &x, &y);
  57.         x--, y--;
  58.         m[x][y]++;
  59.     }
  60.  
  61.     pr[0][0] = m[0][0];
  62.     FOR(i, l)
  63.         FOR(j, w)
  64.         {
  65.             if (i == 0 && j == 0) continue;
  66.             if (i == 0)
  67.             {
  68.                 pr[i][j] = pr[i][j - 1] + m[i][j];
  69.                 continue;
  70.             }
  71.             if (j == 0)
  72.             {
  73.                 pr[i][j] = pr[i - 1][j] + m[i][j];
  74.                 continue;
  75.             }
  76.             pr[i][j] = m[i][j] + pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];
  77.         }
  78.     /*FOR(i, l)
  79.     {
  80.         FOR(j, w)
  81.             cout << pr[i][j] << ' ';
  82.         cout << '\n';
  83.     }*/
  84.  
  85.     FOR(i, l) ml[i] = INF;
  86.     FOR(i, l) mr[i] = INF;
  87.  
  88.  
  89.     FOR(i, l)
  90.         for (int j = i; j < l; ++j)
  91.         {
  92.             int b = 0;
  93.             for (int t = 0; t < w; ++t)
  94.             {
  95.                 while (b < t && ((getS(i, b, j, t) > k) || (getS(i, b, j, b) == 0))) b++;
  96.                 if (getS(i, b, j, t) == k)
  97.                 {
  98.                     ml[j] = min(ml[j], getP(i, b, j, t));
  99.                     mr[i] = min(mr[i], getP(i, b, j, t));
  100.                 }
  101.             }
  102.         }
  103.  
  104.  
  105.  
  106.     int ans = INF;
  107.     for (int i = 0; i < l - 1; ++i)
  108.     {
  109.         int min1 = INF;
  110.         FOR(j, i + 1)
  111.             min1 = min(min1, ml[j]);
  112.         int min2 = INF;
  113.         for (int j = i + 1; j < l; ++j)
  114.             min2 = min(min2, mr[j]);
  115.         ans = min(ans, min1 + min2);
  116.     }
  117.  
  118.     FOR(i, w) ml[i] = INF;
  119.     FOR(i, w) mr[i] = INF;
  120.  
  121.     FOR(i, w)
  122.         for (int j = i; j < w; ++j)
  123.         {
  124.             int b = 0;
  125.             for (int t = 0; t < l; ++t)
  126.             {
  127.                 while (b < t && ((getS(b, i, t, j) > k) || (getS(b, i, b, j) == 0))) b++;
  128.                 if (getS(b, i, t, j) == k)
  129.                 {
  130.                     ml[j] = min(ml[j], getP(b, i, t, j));
  131.                     mr[i] = min(mr[i], getP(b, i, t, j));
  132.                 }
  133.             }
  134.         }
  135.  
  136.     for (int i = 0; i < w - 1; ++i)
  137.     {
  138.         int min1 = INF;
  139.         FOR(j, i + 1)
  140.             min1 = min(min1, ml[j]);
  141.         int min2 = INF;
  142.         for (int j = i + 1; j < w; ++j)
  143.             min2 = min(min2, mr[j]);
  144.         ans = min(ans, min1 + min2);
  145.     }
  146.  
  147.     if (ans == INF)
  148.         cout << "NO";
  149.     else cout << ans;
  150.  
  151.     return 0;
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top