fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. // limit
  4. #define mod1 22439423LL
  5. #define mod2 42342432LL
  6. #define mod3 56454765LL
  7. #define mod4 66867574LL
  8. #define oo 1000000001
  9. #define OO 1000000000000000007LL
  10. #define maxN 107
  11.  
  12. // loop
  13. #define fto(i, x, y) for(int i = (x); i <= (y); ++i)
  14. #define fdto(i, x, y) for(int i = (x); i >= (y); --i)
  15. #define ftoa(i, x, y, a) for(int i = (x); i <= (y); i += a)
  16. #define fdtoa(i, x, y, a) for(int i = (x); i >= (y); i -= a)
  17. #define ftosqrt(i, x, y) for(int i = (x); i*i <= (y); ++i)
  18. #define ftoit(it, var) for (__typeof(var.begin()) it = var.begin(); it != var.end(); ++it)
  19. #define fdtoit(rit, var) for (__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); ++rit)
  20.  
  21. // debug
  22. #define debug cout << "*" << endl;
  23. #define bug1d(a, x, y) { cout << #a << ": "; fto(_, x, y) cout << a[_] << ' '; cout << endl; }
  24. #define bug2d(a, x, y, u, v) { cout << #a << ": " << endl; fto(i, x, y) {fto(j, u, v) cout << a[i][j] << ' '; cout << endl;}; cout << endl;}
  25. #define bug(a) cout << #a << " = " << a << endl;
  26. #define bug2(a, b) cout << #a << " = " << a << "; "; cout << #b << " = " << b << endl;
  27. #define bug3(a, b, c) cout << #a << " = " << a << "; "; cout << #b << " = " << b << "; "; cout << #c << " = " << c << endl;
  28.  
  29. // operation
  30. #define mp make_pair
  31. #define pb push_back
  32. #define pf push_front
  33. // structure
  34. #define ii pair<int, int>
  35. #define iii pair<ii, int>
  36. #define vi vector<int>
  37. #define vll vector<ll>
  38. #define vii vector<ii>
  39. #define matrix vector<vi>
  40.  
  41. // get value
  42. #define FF first
  43. #define SS second
  44.  
  45. // data type
  46. #define ll long long
  47. #define ull unsigned long long
  48.  
  49. // function
  50. #define lb lower_bound
  51. #define ub upper_bound
  52.  
  53. // const value
  54. #define pi 3.14159265358979323846264338327950288419716939937510
  55.  
  56. using namespace std;
  57.  
  58. template <class T>
  59. T min(T a, T b, T c) {
  60.     return min(a, min(b, c));
  61. }
  62.  
  63. template <class T>
  64. T min(T a, T b, T c, T d) {
  65.     return min(a, min(b, min(c, d)));
  66. }
  67.  
  68. template <class T>
  69. T max(T a, T b, T c) {
  70.     return max(a, max(b, c));
  71. }
  72.  
  73. template <class T>
  74. T max(T a, T b, T c, T d) {
  75.     return max(a, max(b, max(c, d)));
  76. }
  77.  
  78. bool cmp(const ii& a, const ii& b) {return (a.FF > b.FF || (a.FF == b.FF && a.SS >= b.SS));}
  79. ll GCD(ll a, ll b) {return (a%b) ? GCD(b, a%b) : b;}
  80.  
  81. const string namePro = "rect";
  82.  
  83. int n, m, k;
  84. int h[maxN], w[maxN];
  85.  
  86. bool isCheck[maxN][maxN];
  87. int ans, res, cnt_fill, cnt_check;
  88.  
  89. ii trace[maxN], bestTrace[maxN];
  90.  
  91. bool inBound(int type, int x, int y) {
  92. 	fto (i, x, x+h[type]-1) {
  93. 		fto (j, y, y+w[type]-1) {
  94.             ++cnt_check;
  95. 			if (isCheck[i][j]) return 0;
  96. 		}
  97. 	}
  98. 	return 1;
  99. }
  100.  
  101. void check(int type, int x, int y) {
  102. 	fto (i, x, x+h[type]-1) {
  103. 		fto (j, y, y+w[type]-1) {
  104. 		    ++cnt_fill;
  105. 			isCheck[i][j] = 1;
  106. 		}
  107. 	}
  108. 	return;
  109. }
  110.  
  111. void uncheck(int type, int x, int y) {
  112. 	fto (i, x, x+h[type]-1) {
  113. 		fto (j, y, y+w[type]-1) {
  114. 		    ++cnt_fill;
  115. 			isCheck[i][j] = 0;
  116. 		}
  117. 	}
  118. 	return;
  119. }
  120.  
  121. void brute_force(int x) {
  122. 	if (x > k) {
  123. 		if (ans < res) {
  124. 			ans = res;
  125. //			int cnt = 0;
  126. 			fto (i, 1, k) {
  127. //			    if (trace[i] != mp(0, 0)) ++cnt;
  128. 			    bestTrace[i] = trace[i];
  129. 			}
  130. //			if (cnt != res) {
  131. //                fto (i, 1, k) cout << trace[i].FF << " " << trace[i].SS << endl;
  132. //                exit(0);
  133. //			}
  134. 		}
  135.  
  136. 		return;
  137. 	}
  138.  
  139. 	if (ans == k) return;
  140. 	fto (i, 1, n-h[x]+1) {
  141. 		fto (j, 1, m-w[x]+1) {
  142. 			bool tmp = inBound(x, i, j);
  143. 			if (tmp) check(x, i, j);
  144.  
  145. 			if (tmp) ++res;
  146. 			if (tmp) trace[x] = mp(i, j);
  147.  
  148. 			if (tmp) brute_force(x+1);
  149. 			trace[x] = mp(0, 0);
  150.  
  151. 			if (tmp) uncheck(x, i, j);
  152. 			if (tmp) --res;
  153. 		}
  154. 	}
  155.  
  156. 	brute_force(x+1);
  157. 	return;
  158. }
  159.  
  160.  
  161. int main() {
  162.     #ifndef ONLINE_JUDGE
  163.         freopen((namePro+".inp").c_str(), "r", stdin);
  164.         freopen((namePro+".out").c_str(), "w", stdout);
  165.     #endif // ONLINE_JUDGE
  166.  
  167.     scanf("%d%d%d", &n, &m, &k);
  168.     fto (i, 1, k) scanf("%d%d", &h[i], &w[i]);
  169.  
  170. 	brute_force(1);
  171. 	//cout << ans << endl;
  172.  
  173.     //cout << cnt_fill << " " << cnt_check << endl;
  174.  
  175. 	printf("%d\n", k);
  176. 	fto (i, 1, k) printf("%d %d\n", bestTrace[i].FF, bestTrace[i].SS);
  177.  
  178.     return 0;
  179. }
  180.  
Success #stdin #stdout 0s 16080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pRlcBI
language:
C++14 (gcc 8.3)
created:
6 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!