lina_os

Untitled

May 1st, 2025
10
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define ld long double
  5.  
  6. using namespace std;
  7.  
  8. ll n,m,k;
  9. vector<vector<vector<ll>>>ps;
  10.  
  11. bool can(ll ms) {
  12. for (ll i=0; i<n-ms+1; i++) {
  13. for (ll j=0; j<m-ms+1; j++) {
  14. ll x=i, y=j, xx=x+ms-1,yy=y+ms-1;
  15. x++; y++; xx++; yy++;
  16. ll kk=0;
  17. for (int l=0; l<26; l++) {
  18. ll f=ps[xx][yy][l]+ps[x-1][y-1][l]-ps[x-1][yy][l]-ps[xx][y-1][l];
  19. if (f) kk++;
  20.  
  21. }
  22. if (kk>=k) return true;
  23. }
  24. }
  25. return false;
  26. }
  27.  
  28. pair<ll,ll> solve(ll ms) {
  29. for (ll i=0; i<n-ms+1; i++) {
  30. for (ll j=0; j<m-ms+1; j++) {
  31. ll x=i, y=j, xx=x+ms-1,yy=y+ms-1;
  32. x++; y++; xx++; yy++;
  33. ll kk=0;
  34. for (int l=0; l<26; l++) {
  35. ll f=ps[xx][yy][l]+ps[x-1][y-1][l]-ps[x-1][yy][l]-ps[xx][y-1][l];
  36. if (f) kk++;
  37. }
  38. if (kk>=k) return {x,y};
  39. }
  40. }
  41. return {-1,-1};
  42. }
  43.  
  44. int main() {
  45. ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  46. cin >> n >> m >> k;
  47. vector<vector<char>>v(n, vector<char>(m));
  48. ps.resize(n + 1, vector<vector<ll>>(m + 1, vector<ll>(26)));
  49. for (auto &i:v)
  50. for (auto &j:i)
  51. cin >> j;
  52.  
  53. // prefix frequency
  54. for (int i=1; i<=n; i++) {
  55. for (int j=1; j<=m; j++) {
  56. for (int l=0; l<26; l++) {
  57. ps[i][j][l]=ps[i-1][j][l]+ps[i][j-1][l]-ps[i-1][j-1][l];
  58. }
  59. ps[i][j][v[i-1][j-1]-'A']++;
  60. }
  61. }
  62.  
  63. // for (int i = 1; i <= n; i++) {
  64. // for (int j = 1; j <= m; j++) {
  65. // cout << "(";
  66. // for (int l = 0; l < 26; l++) {
  67. // cout << ps[i][j][l] << " ";
  68. // }
  69. // cout << endl;
  70. // }
  71. // cout << ") ";
  72. // cout << endl;
  73. // }
  74. //binary search on minimum side length
  75. ll l=1,r=min(n,m),mid;
  76. while (l<=r) {
  77. mid=(l+r)/2;
  78. if (can(mid)) {
  79. if (mid==1 || !can(mid-1)) {
  80. pair<ll,ll>x(solve(mid));
  81. cout << mid << endl << x.first << ' ' << x.second << endl;
  82. return 0;
  83. }
  84. else r=mid-1;
  85. }
  86. else l=mid+1;
  87. }
  88. cout << -1 << endl;
  89. return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment