Guest User

Untitled

a guest
Aug 9th, 2015
191
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <assert.h>
  3. #include <unordered_map>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef vector < long long > vll;
  9. typedef pair < long long, long long > pll;
  10. typedef pair < int, int > pii;
  11. typedef vector < int > vii;
  12.  
  13. #define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
  14. #define l(x) (((x) << 1) | 1)
  15. #define r(x) ((l(x)) + 1)
  16. #define mp make_pair
  17. #define fst first
  18. #define snd second
  19.  
  20. ll t, n, u, v, m, q, r, ql, qr, k, l, s, x, y, w;
  21. const int N = 300;
  22. const long long mod = 1e9 + 7;
  23. const long long INF = 1LL << 57LL;
  24. const bool JUDGE = false;
  25. ll _n;
  26. int g[N][N];
  27. int gt[N][N];
  28. int pre[N][N];
  29. ll per[N];
  30. inline int cnt(int xa, int ya, int xb, int yb) {
  31.     int ret = pre[xb][yb] - pre[xa - 1][yb] - pre[xb][ya - 1] + pre[xa - 1][ya - 1];
  32.     return ret;
  33. }
  34. int main(){
  35.     csl;
  36.     if (JUDGE) {
  37.         freopen("in.txt", "r", stdin);
  38.         freopen("out.txt", "w", stdout);
  39.     }
  40.     cin >> n >> m;
  41.     cin >> _n >> k;
  42.     for (int i = 0; i < _n; ++i) {
  43.         cin >> x >> y;
  44.         g[x][y]++;
  45.         gt[y][x]++;
  46.     }
  47.     for (int i = 1; i <= n; ++i) {
  48.         for (int j = 1; j <= m; ++j) {
  49.             pre[i][j] = g[i][j] - pre[i - 1][j - 1] + pre[i - 1][j] + pre[i][j - 1];
  50.         }
  51.     }
  52.     ll ans = INF;
  53.     per[0] = INF;
  54.     for (ll i = 1; i <= n; ++i) {
  55.         per[i] = INF;
  56.         for (ll j = i; j > 0; --j) {
  57.             int l = 1, r = 1;
  58.             int curcnt = cnt(j, l, i, r);
  59.             while (r < n + 1 && l < n + 1) {
  60.                 while (r < n + 1 && curcnt < k) {
  61.                     r++;
  62.                     curcnt = cnt(j, l, i, r);
  63.                 }
  64.                 if (r == n + 1) continue;
  65.                 while (curcnt >= k && l < n + 1) {
  66.                     if (curcnt == k) {
  67.                         per[i] = min(per[i], 2 * (i - j + 1) + 2 * (r - l + 1));
  68.                     }
  69.                     l++;
  70.                     curcnt = cnt(j, l, i, r);
  71.                 }
  72.             }
  73.             ans = min(ans, per[i] + per[j - 1]);
  74.         }
  75.         //cout << per[i] << '\n';
  76.         per[i] = min(per[i], per[i - 1]);
  77.     }
  78.     swap(n, m);
  79.     for (int i = 1; i <= n; ++i) {
  80.         for (int j = 1; j <= m; ++j) g[i][j] = gt[i][j];
  81.     }
  82.     memset(pre, 0, sizeof(pre));
  83.     for (int i = 1; i <= n; ++i) {
  84.         for (int j = 1; j <= m; ++j) {
  85.             pre[i][j] = g[i][j] - pre[i - 1][j - 1] + pre[i - 1][j] + pre[i][j - 1];
  86.         }
  87.     }
  88.     per[0] = INF;
  89.     for (ll i = 1; i <= n; ++i) {
  90.         per[i] = INF;
  91.         for (ll j = i; j > 0; --j) {
  92.             int l = 1, r = 1;
  93.             int curcnt = cnt(j, l, i, r);
  94.             while (r < n + 1 && l < n + 1) {
  95.                 while (r < n + 1 && curcnt < k) {
  96.                     r++;
  97.                     curcnt = cnt(j, l, i, r);
  98.                 }
  99.                 if (r == n + 1) continue;
  100.                 while (curcnt >= k && l < n + 1) {
  101.                     if (curcnt == k) {
  102.                         per[i] = min(per[i], 2 * (i - j + 1) + 2 * (r - l + 1));
  103.                     }
  104.                     l++;
  105.                     curcnt = cnt(j, l, i, r);
  106.                 }
  107.             }
  108.             ans = min(ans, per[i] + per[j - 1]);
  109.         }
  110.     //  cout << per[i] << '\n';
  111.         per[i] = min(per[i], per[i - 1]);
  112.     }
  113.     if (ans != INF) cout << ans << '\n';
  114.     else cout << "NO\n";
  115.     return 0;
  116. }
RAW Paste Data