MinhNGUYEN2k4

Untitled

Oct 16th, 2021
834
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 3005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int r, c, h, w;
  28. int p[N][N];
  29. int new_p[N][N];
  30. int pre[N][N];
  31. int sub1 = 0;
  32. int ans = 0;
  33.  
  34. void readfile()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0);cout.tie(0);
  38.     if (fopen(Task".inp","r"))
  39.     {
  40.         freopen(Task".inp","r",stdin);
  41.         //freopen(Task".out","w",stdout);
  42.     }
  43.     cin >> r >> c >> h >> w;
  44.     for(int i=1; i<=r; i++){
  45.         for(int j=1; j<=c; j++){
  46.             cin >> p[i][j];
  47.             sub1 = max(sub1,p[i][j]);
  48.         }
  49.     }
  50. }
  51.  
  52. void sub2(){
  53.     vector<int> val;
  54.     for(int i=1; i<=r; i++){
  55.         for(int j=1; j<=c; j++){
  56.             val.pb(p[i][j]);
  57.         }
  58.     }
  59.     sort(all(val));
  60.     //for(auto x : val) cout << x << ' ';
  61.     //cout << endl;
  62.     cout << val[val.size()/2];
  63. }
  64.  
  65. void solve(int x, int y){
  66.     int u = x + h - 1;
  67.     int v = y + w - 1;
  68.     vector<int> val;
  69.     for(int i=x; i<=u; i++){
  70.         for(int j=y; j<=v; j++){
  71.             val.pb(p[i][j]);
  72.         }
  73.     }
  74.     sort(all(val));
  75.     //cout << x << ' ' << y << ": ";
  76.     //cout << val[val.size()/2] << endl;
  77.     ans = max(ans,val[val.size()/2]);
  78. }
  79.  
  80. void sub3(){
  81.     for(int i=1; i+h-1<=r; i++){
  82.         for(int j=1; j+w-1<=c; j++){
  83.             solve(i,j);
  84.         }
  85.     }
  86.     cout << ans;
  87. }
  88.  
  89. int get_sum(int x, int y, int u, int v){
  90.     return pre[u][v] - pre[u][y-1] - pre[x-1][v] + pre[x-1][y-1];
  91. }
  92.  
  93. bool ok(int val){
  94.     for(int i=1; i<=r; i++){
  95.         for(int j=1; j<=c; j++){
  96.             new_p[i][j] = (p[i][j]<val ? 0 : 1);
  97.             //cout << new_p[i][j] << " \n"[j==c];
  98.         }
  99.     }
  100.     memset(pre, 0, sizeof pre);
  101.     for(int i=1; i<=r; i++){
  102.         for(int j=1; j<=c; j++){
  103.             pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + new_p[i][j];
  104.         }
  105.     }
  106.     ans = 0;
  107.     for(int i=1; i+h-1 <= r; i++){
  108.         for(int j=1; j+w-1 <= c; j++){
  109.             int x = i+h-1;
  110.             int y = j+w-1;
  111.             ans = max(ans,get_sum(i,j,x,y));
  112.         }
  113.     }
  114.     return ans>(h*w/2);
  115. }
  116.  
  117. void proc()
  118. {
  119.     if (h==w && w==1) cout << sub1;
  120.     else if (h==r && w==c){
  121.         sub2();
  122.     }
  123.     else if (r <= 30 && c <= 30){
  124.         sub3();
  125.     }
  126.     else{
  127.         int lo = 1, hi = r*c;
  128.         while (hi - lo > 0){
  129.             int mid = (lo+hi+1)/2;
  130.             if (ok(mid)){
  131.                 lo = mid;
  132.             }
  133.             else hi = mid-1;
  134.         }
  135.         cout << lo;
  136.     }
  137. }
  138.  
  139. signed main()
  140. {
  141.     readfile();
  142.     proc();
  143.     return 0;
  144. }
  145.  
RAW Paste Data