Advertisement
skimono

Untitled

Jun 21st, 2022
1,004
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef long double ld;
  8. typedef string str;
  9. //typedef __int128 ultraint;
  10. #define endl "\n"
  11. #define sqrt sqrtl
  12. //#define pow fast_pow
  13.  
  14. const ll inf = (ll)1e18 + 7;
  15. ld eps = 1e-6;
  16. ld Pi = 3.14159265358979323846;
  17.  
  18. signed main() {
  19.     ios_base::sync_with_stdio(0);
  20.     cin.tie(NULL);
  21.     cout.tie(NULL);
  22.     ll t = 1;
  23.     //cin >> t
  24.     while (t--) {
  25.         ll u, d, m, i, j, y, z;
  26.         cin >> u >> d >> m;
  27.         set <char> x;
  28.         pair <ll, ll> ans = { 0,1 }, elem;
  29.         char h;
  30.         string s;
  31.         cin >> s;
  32.         for (i = 0; i < s.size(); i++) {
  33.             x.insert(s[i]);
  34.         }
  35.         vector <vector <ll> > a(u + 1, vector <ll>(d + 1));
  36.         vector <vector <ll> > c(u + 1, vector <ll>(d + 1));
  37.         for (i = 1; i <= u; i++) {
  38.             for (j = 1; j <= d; j++) {
  39.                 cin >> h;
  40.                 if (x.count(h)) {
  41.                     a[i][j] = 1;
  42.                 }
  43.             }
  44.         }
  45.         for (j = 1; j <= d; j++) {
  46.             c[1][j] = c[1][j - 1] + a[1][j];
  47.         }
  48.         for (i = 1; i <= u; i++) {
  49.             c[i][1] = c[i - 1][1] + a[i][1];
  50.         }
  51.         for (i = 2; i <= u; i++) {
  52.             for (j = 2; j <= d; j++) {
  53.                 c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + a[i][j];
  54.             }
  55.         }
  56.         for (i = 1; i <= u; i++) {
  57.             for (j = 1; j <= d; j++) {
  58.                 for (y = i + m - 1; y <= u; y++) {
  59.                     for (z = j + m - 1; z <= d; z++) {
  60.                         elem.first = c[y][z] - c[i - 1][z] - c[y][j - 1] + c[i - 1][j - 1];
  61.                         elem.second = (y - i + 1) * (z - j + 1);
  62.                         if (ans.first * elem.second - ans.second * elem.first < 0) {
  63.                             ans = elem;
  64.                         }
  65.                         else if (ans.first * elem.second - ans.second * elem.first == 0 && elem.second > ans.second) {
  66.                             ans = elem;
  67.                         }
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.         cout << ans.first << "/" << ans.second << endl;
  73.     }
  74. }
  75. //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement