Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- using namespace std;
- ll n,m,k;
- vector<vector<vector<ll>>>ps;
- bool can(ll ms) {
- for (ll i=0; i<n-ms+1; i++) {
- for (ll j=0; j<m-ms+1; j++) {
- ll x=i, y=j, xx=x+ms-1,yy=y+ms-1;
- x++; y++; xx++; yy++;
- ll kk=0;
- for (int l=0; l<26; l++) {
- ll f=ps[xx][yy][l]+ps[x-1][y-1][l]-ps[x-1][yy][l]-ps[xx][y-1][l];
- if (f) kk++;
- }
- if (kk>=k) return true;
- }
- }
- return false;
- }
- pair<ll,ll> solve(ll ms) {
- for (ll i=0; i<n-ms+1; i++) {
- for (ll j=0; j<m-ms+1; j++) {
- ll x=i, y=j, xx=x+ms-1,yy=y+ms-1;
- x++; y++; xx++; yy++;
- ll kk=0;
- for (int l=0; l<26; l++) {
- ll f=ps[xx][yy][l]+ps[x-1][y-1][l]-ps[x-1][yy][l]-ps[xx][y-1][l];
- if (f) kk++;
- }
- if (kk>=k) return {x,y};
- }
- }
- return {-1,-1};
- }
- int main() {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- cin >> n >> m >> k;
- vector<vector<char>>v(n, vector<char>(m));
- ps.resize(n + 1, vector<vector<ll>>(m + 1, vector<ll>(26)));
- for (auto &i:v)
- for (auto &j:i)
- cin >> j;
- // prefix frequency
- for (int i=1; i<=n; i++) {
- for (int j=1; j<=m; j++) {
- for (int l=0; l<26; l++) {
- ps[i][j][l]=ps[i-1][j][l]+ps[i][j-1][l]-ps[i-1][j-1][l];
- }
- ps[i][j][v[i-1][j-1]-'A']++;
- }
- }
- // for (int i = 1; i <= n; i++) {
- // for (int j = 1; j <= m; j++) {
- // cout << "(";
- // for (int l = 0; l < 26; l++) {
- // cout << ps[i][j][l] << " ";
- // }
- // cout << endl;
- // }
- // cout << ") ";
- // cout << endl;
- // }
- //binary search on minimum side length
- ll l=1,r=min(n,m),mid;
- while (l<=r) {
- mid=(l+r)/2;
- if (can(mid)) {
- if (mid==1 || !can(mid-1)) {
- pair<ll,ll>x(solve(mid));
- cout << mid << endl << x.first << ' ' << x.second << endl;
- return 0;
- }
- else r=mid-1;
- }
- else l=mid+1;
- }
- cout << -1 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment