Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cassert>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <list>
- #include <map>
- #include <queue>
- #include <set>
- #include <string>
- #include <sstream>
- #include <vector>
- #include <complex>
- #include <ctime>
- #include <stack>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef vector<int> VI;
- typedef vector< VI > VVI;
- typedef pair<int, int> PII;
- typedef vector<PII> VPII;
- #define REP(i, n) for(int i = 0; i < n; ++i)
- #define RREP(i, n) for(int i = n - 1; i >= 0; --i)
- #define FOR(i, x, y) for(int i = x; i <= y; ++i)
- #define RFOR(i, x, y) for(int i = x; i >= y; --i)
- #define SZ(a) (int)(a).size()
- #define ALL(a) (a).begin(),(a).end()
- #define SORT(a) sort(ALL(a))
- #define CLEAR(x) memset(x, 0, sizeof x);
- #define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
- #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
- #define pb push_back
- #define mk make_pair
- #define sqr(x) (x)*(x)
- #define X first
- #define Y second
- const long double pi=acos(-1.0);
- const long double eps = 1e-6;
- const int inf = 1e+9;
- const int N = 1e+4;
- int n, m, k;
- string s1;
- string mp[51];
- bool dp[50][50];
- int sum[51][51];
- int query (int x1, int y1, int x2, int y2) {
- if (x1 == 0 && y1 == 2 && x2 == 2 && y2 == 12)
- int r = 2;
- int res = sum[x2][y2];
- if (x1 >= 1)
- res -= sum[x1 - 1][y2];
- if (y1 >= 1)
- res -= sum[x2][y1 - 1];
- if (x1 - 1 >= 0 && y1 - 1 >= 0)
- res += sum[x1 - 1][y1 - 1];
- return res;
- }
- int main () {
- cin >> n >> m >> k >> s1;
- REP (i, n)
- cin >> mp[i];
- REP (i, n)
- REP (j, m) {
- bool f = 0;
- REP (i1, SZ(s1))
- if (s1[i1] == mp[i][j]) {
- f = 1;
- break;
- }
- if (f)
- dp[i][j] = 1;
- }
- sum[0][0] = dp[0][0];
- FOR (i, 1, n - 1)
- sum[i][0] = sum[i - 1][0] + dp[i][0];
- FOR (j, 1, m - 1)
- sum[0][j] = sum[0][j - 1] + dp[0][j];
- FOR (i, 1, n - 1)
- FOR (j, 1, m - 1)
- sum[i][j] += sum[i][j - 1] + sum[i - 1][j] + dp[i][j] - sum [i - 1][j - 1];
- double maxx = 0;
- int an = 0;
- int sz = -1;
- FOR (i, 0, n - 1)
- FOR (j, 0, m - 1)
- FOR (x, k, n)
- FOR (y, k, m) {
- if (i + x - 1 > n - 1 || j + y - 1> m - 1)
- continue;
- double p = query (i, j, i + x - 1, j + y - 1);
- double t = p / (x * y);
- if (t > maxx) {
- maxx = t;
- an = p;
- sz = x * y;
- } else if (t == maxx && (x * y) > sz) {
- an = p;
- sz = x * y;
- }
- }
- cout << an << "/" << sz;
- return 0;
- }
- /*
- 5
- -15 -22 21 -211 -2112
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement