• API
• FAQ
• Tools
• Archive
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.
Top