Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <cassert>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long tint;
  9.  
  10. #define forsn(i, s, n) for(int i=s;i<int(n);i++)
  11. #define forn(i, n) forsn(i, 0, n)
  12. #define all(v) v.begin(),v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define NACHO ios::sync_with_stdio(0); cin.tie(NULL);
  15. #define dbg cout << "hu" << endl;
  16.  
  17. const tint INF = 11000000;
  18. const int MOD = 1000000007;
  19.  
  20. int pinos[2001][2001];
  21. int frutas[2001][2001];
  22. int SP[2001][2001];
  23. int SF[2001][2001];
  24.  
  25. int main(){
  26.     NACHO;
  27.     //ifstream cin("frutales.in");
  28.     //ofstream cout("frutales.out");
  29.     int n, m, p, f; cin >> n >> m >> p >> f;
  30.     forn(i, p){
  31.         int x, y; cin >> x >> y;
  32.         pinos[x-1][y-1] = 1;
  33.     }
  34.     forn(i, f){
  35.         int x, y; cin >> x >> y;
  36.         frutas[x-1][y-1] = 1;
  37.     }
  38.     forsn(i, 1, n+1){
  39.         forsn(j, 1, m+1){
  40.             SP[i][j] = SP[i-1][j]+SP[i][j-1]-SP[i-1][j-1]+pinos[i-1][j-1];
  41.         }
  42.     }
  43.     forsn(i, 1, n+1){
  44.         forsn(j, 1, m+1){
  45.             SF[i][j] = SF[i-1][j]+SF[i][j-1]-SF[i-1][j-1]+frutas[i-1][j-1];
  46.         }
  47.     }
  48.     int posX = -1, posY = -1;
  49.     int maxi = -1;
  50.     int base = -1;
  51.     forsn(i, 1, n+1){
  52.         forsn(j, 1, m+1){
  53.             int low = 0, high = min(n-i, m-j)+1;
  54.             while(high-low > 1){
  55.                 int mid = (high+low)/2;
  56.                 if(SP[i+mid][j+mid]-SP[i-1][j+mid]-SP[i+mid][j-1]+SP[i-1][j-1] > 0) high = mid;
  57.                 else low = mid;
  58.             }
  59.             int low2 = 0, high2 = low;
  60.             int act = SF[i+low][j+low]-SF[i-1][j+low]-SF[i+low][j-1]+SF[i-1][j-1];
  61.             while(high2-low2 > 1){
  62.                 int mid = (low2+high2)/2;
  63.                 if(act == SF[i+mid][j+mid]-SF[i-1][j+mid]-SF[i+mid][j-1]+SF[i-1][j-1]){
  64.                     high2 = mid;
  65.                 }else low2 = mid;
  66.             }
  67.             if(act == maxi && high2 < base){
  68.                 base = high2+1;
  69.                 posX = i;
  70.                 posY = j;
  71.             }else if(act > maxi){
  72.                 maxi = act;
  73.                 base = high2+1;
  74.                 posX = i;
  75.                 posY = j;
  76.             }
  77.         }
  78.     }
  79.     cout << posX-1 << " " << posY-1 << "\n";
  80.     cout << base << "\n";
  81.     cout << maxi << "\n";
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement