Source code for submission s827

Go to diff to previous submission

fm.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17.  
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25. const int INF = 1<<29;
  26.  
  27. typedef long long ll;
  28.  
  29. const int MAXN = 1400;
  30. bool input[MAXN][MAXN];
  31. bool rowmax[MAXN][MAXN];
  32. bool cellmax[MAXN][MAXN];
  33.  
  34. int AR, AC, TR, TC;
  35.  
  36. int main() {
  37. while (scanf("%d%d%d%d ", &AR, &AC, &TR, &TC) == 4) {
  38. REP(r,MAXN) REP(c,MAXN) {
  39. input[r][c] = false;
  40. rowmax[r][c] = false;
  41. cellmax[r][c] = false;
  42. }
  43. REP(i,AR) {
  44. char *line = 0;
  45. size_t size;
  46. getline(&line, &size, stdin);
  47. REP(j,AC) input[i][j] = (line[j] == 'X');
  48. free(line);
  49. }
  50. REP(r,AR) {
  51. int sum = 0;
  52. int begin = -TC;
  53. int end = 0;
  54. while (end < AC+TC) {
  55. if (begin >= 0) sum -= input[r][begin];
  56. sum += input[r][end];
  57. rowmax[r][end] = (sum > 0);
  58. ++begin; ++end;
  59. }
  60. }
  61. REP(c,AC+TC) {
  62. int sum = 0;
  63. int begin = -TR;
  64. int end = 0;
  65. while (end < AR+TR) {
  66. if (begin >= 0) sum -= rowmax[begin][c];
  67. sum += rowmax[end][c];
  68. cellmax[end][c] = (sum > 0);
  69. ++begin; ++end;
  70. }
  71. }
  72. int best = INF;
  73. REP(sc,TC) REP(sr,TR) {
  74. int cnt = 0;
  75. int r = sr;
  76. while (r < AR+TR) {
  77. int c = sc;
  78. while (c < AC+TC) {
  79. cnt += (cellmax[r][c] ? 1 : 0);
  80. c += TC;
  81. }
  82. r += TR;
  83. }
  84. if (cnt < best) best = cnt;
  85. }
  86. printf("%d\n", best);
  87. }
  88. return 0;
  89. }
  90.  

Diff to submission s797

fm.cpp

--- c5.s797.cteam010.fm.cpp.0.fm.cpp
+++ c5.s827.cteam010.fm.cpp.0.fm.cpp
@@ -36,9 +36,13 @@
 int main() {
         while (scanf("%d%d%d%d ", &AR, &AC, &TR, &TC) == 4) {
+                REP(r,MAXN) REP(c,MAXN) {
+                        input[r][c] = false;
+                        rowmax[r][c] = false;
+                        cellmax[r][c] = false;
+                }
                 REP(i,AR) {
                         char *line = 0;
                         size_t size;
                         getline(&line, &size, stdin);
-                        DEBUG(line);
                         REP(j,AC) input[i][j] = (line[j] == 'X');
                         free(line);
@@ -78,7 +82,4 @@
                                 r += TR;
                         }
-                        DEBUG(sc);
-                        DEBUG(sr);
-                        DEBUG(cnt);
                         if (cnt < best) best = cnt;
                 }