fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 3005;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int n, a[N][N], m, h, w, pre[N][N];
  39.  
  40. inline void Read_Input() {
  41.     cin >> n >> m >> h >> w;
  42.     FOR(i, 1, n)
  43.         FOR(j, 1, m)
  44.             cin >> a[i][j];
  45. }
  46.  
  47. int Get(int x, int y, int xx, int yy) {
  48.     return pre[xx][yy] - pre[x - 1][yy] - pre[xx][y - 1] + pre[x - 1][y - 1];
  49. }
  50.  
  51. bool check (int Median) {
  52.     FOR(i, 1, n)
  53.         FOR(j, 1, m)
  54.             if (a[i][j] >= Median)
  55.                 pre[i][j] = 1;
  56.             else pre[i][j] = -1;
  57.  
  58.     /// build prefix_sum 2 chieu
  59.  
  60.     FOR(i, 1, n)
  61.         FOR(j, 1, m)
  62.             pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + pre[i][j];
  63.  
  64.     FOR(i, 1, n - h + 1)
  65.         FOR(j, 1, m - w + 1) {
  66.             /// o(i, j) = trai tren
  67.             int xx = i + h - 1;
  68.             int yy = j + w - 1;
  69.             if (Get(i, j, xx, yy) > 0) return true;
  70.         }
  71.     return false;
  72. }
  73.  
  74. inline void Solve() {
  75.     if (h == 1 && w == 1) {
  76.         /// toi dang xu li subtask 1
  77.         /// if de dam bao rang TH nay chinh xac la subtask 1
  78.  
  79.         int Ans = 0;
  80.         FOR(i, 1, n)
  81.             FOR(j, 1, m) {
  82.                 /// o(i, j)
  83.                 /// a[i][j] chinh xac la trung vi
  84.  
  85.                 Ans = max(Ans, a[i][j]);
  86.             }
  87.         cout << Ans;
  88.         return;
  89.     }
  90.     else if (h == n && w == m) {
  91.         /// subtask 2
  92.         vector<int> V;
  93.         FOR(i, 1, n)
  94.             FOR(j, 1, m)
  95.                 V.push_back(a[i][j]);
  96.  
  97.         sort(V.begin(), V.end());
  98.  
  99.         int sz = V.size();
  100.         cout << V[sz / 2];
  101.         return;
  102.     }
  103.     else {
  104.         /// subtask cuoi
  105.         /// theo khuon mau cua bai B
  106.  
  107.         /// chat nhi phan
  108.  
  109.         int l = 1, r = n * m;
  110.         /// thay doi viec lay trung vi
  111.         /// tu 1 chieu -> 2 chieu
  112.         /// prefixsum 1 chieu  - tong cua doan [L, R] >= 0
  113.  
  114.         /// o(x, y) -> o(xx, yy)
  115.  
  116.         /// do do toi thay doi thanh prefix_sum 2 chieu
  117.         int Ans = -1;
  118.  
  119.         while (l <= r) {
  120.             int mid = (l + r) >> 1;
  121.             if (check(mid)) {
  122.                 l = mid + 1;
  123.                 Ans = mid;
  124.             }
  125.             else r = mid - 1;
  126.         }
  127.         cout << Ans;
  128.     }
  129. }
  130.  
  131. Ti20_ntson {
  132. //    freopen(TASK".INP","r",stdin);
  133. //    freopen(TASK".OUT","w",stdout);
  134.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  135.     int T = 1;
  136. //    cin >> T;
  137.     while (T -- ) {
  138.         Read_Input();
  139.         Solve();
  140.     }
  141. }
  142.  
  143.  
  144.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Nl6f05
language:
C++14 (gcc 8.3)
created:
44 days 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!