Iamtui1010

landk

Nov 29th, 2021
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ----------- define --------------
  5. #define int long long
  6. #define vi vector<int>
  7. #define ii pair<int,int>
  8. #define fi first
  9. #define sc second
  10. #define mp make_pair
  11. #define pqueue priority_queue
  12. #define popcnt __builtin_popcount
  13. #define getBit(x, k) ((x >> k) & 1)
  14. #define xorBit(x, k) (x ^ (1 << k))
  15. #define siz(x) (int)((x).size())
  16. #define all(x) (x).begin(),(x).end()
  17. // ---------------------------------
  18.  
  19. void Main() {
  20.   int s, n;
  21.   cin >> s >> n;
  22.   vector<vi> a(n + 1, vi(n + 1));
  23.  
  24.   for (int i = 1; i <= n; i++)
  25.     for (int j = 1; j <= n; j++)
  26.     {
  27.       cin >> a[i][j];
  28.       a[i][j] += a[i - 1][j];
  29.     }
  30.  
  31.   int ans = 0, x1, y1, x2, y2;
  32.   for (int i = 1; i <= n; i++)
  33.     for (int j = i; j <= n; j++)
  34.     {
  35.       int sum = 0, l = 1;
  36.       for (int k = 1; k <= n; k++)
  37.       {
  38.         sum += a[j][k] - a[i - 1][k];
  39.         while (sum > 2*s) {
  40.           sum -= a[j][l] - a[i - 1][l];
  41.           l++;
  42.         }
  43.         if (sum >= s)
  44.         {
  45.           long are = (j - i + 1) * (k - l + 1);
  46.           if (are > ans)
  47.           {
  48.             ans = are;
  49.             x1 = l; y1 = i;
  50.             x2 = k; y2 = j;
  51.           }
  52.         }
  53.       }
  54.   }
  55.   //cout << ans << '\n';
  56.   if (ans == 0)
  57.     cout << "NIE" << endl;
  58.   else
  59.     cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
  60. }
  61.  
  62. signed main() {
  63.   //freopen("LAND.inp", "r", stdin );
  64.   //freopen("LAND.out", "w", stdout);
  65.   cin.tie(0)->sync_with_stdio(0);
  66.   int T = 1;
  67.   // cin >> T;
  68.   while (T--) Main();
  69. }
Advertisement
Add Comment
Please, Sign In to add comment