fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <deque>
  7. #include <utility>
  8. #include <set>
  9. #include <map>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include<algorithm>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #define IOF ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  16. #define ll long long
  17. #define ld long double
  18. #define cy cout << "YES" << '\n';
  19. #define cn cout << "NO" << '\n';
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  28. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  29. int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
  30. int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N =2e5+5;
  33. const ll MOD = 998244353;
  34. void FOI(){
  35.     freopen("input.txt", "r" , stdin);
  36.     freopen("output.txt", "w" , stdout);
  37. }
  38.  
  39. //check ur idea
  40.  
  41.  
  42. void solve(){
  43.  
  44. int n , m , a , b ; cin >> n >> m >> a >> b;
  45. map<char , int> frq , frq1;
  46. string s ; cin >> s;
  47. char grid[n][m] ,grid1[m][n];
  48. for(int i = 0 ; i < n ; i++){
  49.     for(int j = 0 ; j < m ; j ++){
  50.         cin >> grid[i][j];
  51.     }
  52. }
  53. for(int i = 0 ; i < m ; i++){
  54.     for(int j = 0 ; j < n ; j++){
  55.         grid1[i][j] = grid[j][i];
  56.     }
  57. }
  58. for(int i = 0 ; i < s.size() ; i++){frq[s[i]]++;}
  59. for(int i = 0 ; i < a ; i++){
  60.     for(int j = 0 ; j < b ; j++)frq1[grid[i][j]]++;
  61. }
  62. ll maxi = 0;
  63. for(int i = 0 ; i <= n-a ; i++){
  64.     for(int j = 0 ; j <= m-b ;  j++){
  65.         int cnt = 1e9;
  66.         for(int k = 0 ; k < 26 ; k++){
  67.             if(frq[k+'a'] == 0)continue;
  68.             if(frq1[k+'a'] == 0){
  69.                 cnt = 0;
  70.                 break;
  71.             }
  72.             cnt = min((frq1[k+'a'])/frq[k+'a'] , cnt);
  73.         }
  74.         maxi = max(maxi , (ll)cnt);
  75.         for(int k = i ; k <= min(a+i , n-1) ; k++){
  76.             frq1[grid[k][j]]--;
  77.             if(b+j < m){
  78.                 frq1[grid[k][b+j]]++;
  79.             }
  80.         }
  81.     }
  82.     frq1.clear();
  83.      for(int j = i+1 ; j <= min(a+i , n-1) ; j++){
  84.     for(int k = 0 ; k < b ; k++)frq1[grid[j][k]]++;
  85. }
  86. }
  87. frq1.clear();
  88. for(int i = 0 ; i < b ; i++){
  89.     for(int j = 0 ; j < a ; j++)frq1[grid1[i][j]]++;
  90. }
  91. for(int i = 0 ; i <= m-b ; i++){
  92.     for(int j = 0 ; j <= n-a ;  j++){
  93.         int cnt = 1e9;
  94.         for(int k = 0 ; k < 26 ; k++){
  95.             if(frq[k+'a'] == 0)continue;
  96.             if(frq1[k+'a'] == 0){
  97.                 cnt = 0;
  98.                 break;
  99.             }
  100.             cnt = min((frq1[k+'a'])/frq[k+'a'] , cnt);
  101.         }
  102.         maxi = max(maxi , (ll)cnt);
  103.         for(int k = i ; k <= min(a+i , n-1) ; k++){
  104.             frq1[grid1[k][j]]--;
  105.             if(b+j < m){
  106.                 frq1[grid1[k][b+j]]++;
  107.             }
  108.         }
  109.     }
  110.     frq1.clear();
  111.      for(int j = i+1 ; j <= min(a+i , n-1) ; j++){
  112.     for(int k = 0 ; k < b ; k++)frq1[grid1[j][k]]++;
  113. }
  114. }
  115. cout << maxi << '\n';
  116. }
  117.  
  118.  
  119.  
  120.  
  121. int main() {
  122.  
  123.  
  124.     IOF
  125.     ll t = 1;
  126.     cin >> t;
  127.     while (t--) {
  128.  
  129.     solve() ;
  130.  
  131.     }
  132.  
  133.     return 0;
  134. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/6WgT0a
language:
C++ (gcc 8.3)
created:
20 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!