Advertisement
MinhNGUYEN2k4

Untitled

Sep 18th, 2021
4,852
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.01 KB | None | 0 0
  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 1005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iii pair<int,ii>
  14. #define iiii pair< ii , ii >
  15. #define viiii vector< iiii >
  16. #define vi vector<int>
  17. #define vii vector< ii >
  18. #define bit(x, i) (((x) >> (i)) & 1)
  19. #define Task "pyramid"
  20. #define int long long
  21.  
  22. using namespace std;
  23.  
  24. typedef long double ld;
  25. typedef vector<iii> viii;
  26. const int inf = 1e10;
  27. const int minf = -1e10;
  28.  
  29. int n,m,a,b,c,d;
  30. int pf[N][N];
  31. int t[N][N];
  32.  
  33. int get(int x, int y, int u, int v){
  34.     return pf[u][v] - pf[u][y-1] - pf[x-1][v] + pf[x-1][y-1];
  35. }
  36.  
  37. void readfile()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0);cout.tie(0);
  41.     if (fopen(Task".inp","r"))
  42.     {
  43.         freopen(Task".inp","r",stdin);
  44.         freopen(Task".out","w",stdout);
  45.     }
  46.     cin >> n >> m >> b >> a >> d >> c;
  47.     for(int i=1; i<=m; i++){
  48.         for(int j=1; j<=n; j++){
  49.             cin >> pf[i][j];
  50.             pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + pf[i][j];
  51.         }
  52.     }
  53.     memset(t, 0x3f3f3f3f3f, sizeof t);
  54.     for(int i=1; i<=m-c+1; i++){
  55.         for(int j=1; j<=n-d+1; j++){
  56.             t[i][j] = get(i,j,i+c-1,j+d-1);
  57.         }
  58.     }
  59. }
  60.  
  61. int fid[N][N];
  62. int f[N][N];
  63. int gid[N][N];
  64. int g[N][N];
  65.  
  66. void proc()
  67. {
  68.     int ans = 0;
  69.     ii p1=ii(-1,-1), p2=ii(-1,-1);
  70.     int lenx = a-c-1;
  71.     int leny = b-d-1;
  72.     for(int i=1; i<=m; i++){
  73.         deque<int> q;
  74.         int hi=1;
  75.         for(int j=1; j+leny-1<=n; j++){
  76.             while (hi<=n && hi<=j+leny-1){
  77.                 while (q.size() && t[i][q.back()]>=t[i][hi]) q.pop_back();
  78.                 q.pb(hi);
  79.                 ++hi;
  80.             }
  81.             while (q.size() && q.front()<j) q.pop_front();
  82.             fid[i][j] = q.front();
  83.             f[i][j] = t[i][q.front()];
  84.         }
  85.     }
  86.     for(int j=1; j<=n; j++){
  87.         deque<int> q;
  88.         int hi=1;
  89.         for(int lo=1; lo+lenx-1<=m; lo++){
  90.             while (hi <= m && hi <= lo+lenx-1){
  91.                 while (q.size() && f[q.back()][j] >= f[hi][j]) q.pop_back();
  92.                 q.pb(hi);
  93.                 hi++;
  94.             }
  95.             while (q.size() && q.front()<lo) q.pop_front();
  96.             gid[lo][j] = q.front();
  97.             g[lo][j] = f[q.front()][j];
  98.         }
  99.     }
  100.     int res=0;
  101.     for(int i=1; i+a-1<=m; i++){
  102.         for(int j=1; j+b-1<=n; j++){
  103.             if (p1.fi==-1||p1.se==-1||get(i,j,i+a-1,j+b-1)-g[i+1][j+1]>res){
  104.                 res = get(i,j,i+a-1,j+b-1)-g[i+1][j+1];
  105.                 p1.fi = i;
  106.                 p1.se = j;
  107.             }
  108.         }
  109.     }
  110.     cout << p1.se << ' ' << p1.fi << '\n';
  111.     p2.fi = gid[p1.fi+1][p1.se+1];
  112.     p2.se = fid[p2.fi][p1.se+1];
  113.     cout << p2.se << ' ' << p2.fi << '\n';
  114. }
  115.  
  116. signed main()
  117. {
  118.     readfile();
  119.     proc();
  120.     return 0;
  121. }
  122.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement