Advertisement
Guest User

Untitled

a guest
Aug 12th, 2013
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.56 KB | None | 0 0
  1.  
  2. #include <algorithm>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <cmath>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <iostream>
  10. #include <list>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <string>
  15. #include <sstream>
  16. #include <vector>
  17. #include <complex>
  18. #include <ctime>
  19. #include <stack>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef vector<int> VI;
  26. typedef vector< VI > VVI;
  27. typedef pair<int, int> PII;
  28. typedef vector<PII> VPII;
  29.  
  30. #define REP(i, n) for(int i = 0; i < n; ++i)
  31. #define RREP(i, n) for(int i = n - 1; i >= 0; --i)
  32. #define FOR(i, x, y) for(int i = x; i <= y; ++i)
  33. #define RFOR(i, x, y) for(int i = x; i >= y; --i)
  34. #define SZ(a) (int)(a).size()
  35. #define ALL(a) (a).begin(),(a).end()
  36. #define SORT(a) sort(ALL(a))
  37. #define CLEAR(x) memset(x, 0, sizeof x);
  38. #define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
  39. #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
  40. #define pb push_back
  41. #define mk make_pair
  42. #define sqr(x) (x)*(x)
  43. #define X first
  44. #define Y second
  45. const long double pi=acos(-1.0);
  46. const long double eps = 1e-6;
  47. const int inf = 1e+9;
  48. const int N = 1e+4;
  49.  
  50. int n, m, k;
  51. string s1;
  52. string mp[51];
  53. bool dp[50][50];
  54. int sum[51][51];
  55. int query (int x1, int y1, int x2, int y2) {
  56. if (x1 == 0 && y1 == 2 && x2 == 2 && y2 == 12)
  57. int r = 2;
  58. int res = sum[x2][y2];
  59. if (x1 >= 1)
  60. res -= sum[x1 - 1][y2];
  61. if (y1 >= 1)
  62. res -= sum[x2][y1 - 1];
  63. if (x1 - 1 >= 0 && y1 - 1 >= 0)
  64. res += sum[x1 - 1][y1 - 1];
  65. return res;
  66. }
  67. int main () {
  68. cin >> n >> m >> k >> s1;
  69. REP (i, n)
  70. cin >> mp[i];
  71. REP (i, n)
  72. REP (j, m) {
  73. bool f = 0;
  74. REP (i1, SZ(s1))
  75. if (s1[i1] == mp[i][j]) {
  76. f = 1;
  77. break;
  78. }
  79. if (f)
  80. dp[i][j] = 1;
  81. }
  82. sum[0][0] = dp[0][0];
  83. FOR (i, 1, n - 1)
  84. sum[i][0] = sum[i - 1][0] + dp[i][0];
  85. FOR (j, 1, m - 1)
  86. sum[0][j] = sum[0][j - 1] + dp[0][j];
  87. FOR (i, 1, n - 1)
  88. FOR (j, 1, m - 1)
  89. sum[i][j] += sum[i][j - 1] + sum[i - 1][j] + dp[i][j] - sum [i - 1][j - 1];
  90. double maxx = 0;
  91. int an = 0;
  92. int sz = -1;
  93. FOR (i, 0, n - 1)
  94. FOR (j, 0, m - 1)
  95. FOR (x, k, n)
  96. FOR (y, k, m) {
  97. if (i + x - 1 > n - 1 || j + y - 1> m - 1)
  98. continue;
  99. double p = query (i, j, i + x - 1, j + y - 1);
  100. double t = p / (x * y);
  101. if (t > maxx) {
  102. maxx = t;
  103. an = p;
  104. sz = x * y;
  105. } else if (t == maxx && (x * y) > sz) {
  106. an = p;
  107. sz = x * y;
  108. }
  109. }
  110. cout << an << "/" << sz;
  111. return 0;
  112. }
  113. /*
  114. 5
  115. -15 -22 21 -211 -2112
  116. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement