fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll; const int N = 2001; int a[ N ][ N ]; ll sum[ N ][ N ];
  6.  
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  10.  
  11.     int a_min = INT_MAX, k, l, n, x0, y0, x1, y1, x2, y2; ll r, s, t; 
  12.  
  13.     cin >> k >> n, l = 2 * k; const string no_solution = "NIE";
  14.  
  15.     for( y0 = 0; y0 < n; y0++ )
  16.         for( int x0 = 0; x0 < n; x0++ )
  17.             cin >> a[ y0 ][ x0 ],
  18.             a_min = min( a_min, a[ y0 ][ x0 ] );
  19.  
  20.     for( y0 = 0, y1 = 1; y0 < n; y0 = y1++ )
  21.         for( x0 = 0, x1 = 1; x0 < n; x0 = x1++ )
  22.         {
  23.             auto &z = sum[ y1 ][ x1 ];
  24.  
  25.             z  =   a[ y0 ][ x0 ],
  26.             z += sum[ y0 ][ x1 ],
  27.             z += sum[ y1 ][ x0 ],
  28.             z -= sum[ y0 ][ x0 ];
  29.         }
  30.  
  31.     if ( sum[ n ][ n ] < k or a_min > l )
  32.     {
  33.        cout << no_solution; return 0;
  34.     }
  35.  
  36.     if ( sum[ n ][ n ] <= l )
  37.     {
  38.        cout << "1 1 " << n << " " << n; return 0;
  39.     }
  40.  
  41.     for( y0 = 0, y1 = 1; y0 < n; y0 = y1++ )
  42.         for( x0 = 0, x1 = 1; x0 < n; x0 = x1++ )
  43.             if ( a[ y0 ][ x0 ] <= l )
  44.             {
  45.                 for( r = sum[ y0 ][ x0 ], y2 = y1; y2 <= n; y2++ )
  46.                     for( s = sum[ y2 ][ x0 ] - r, x2 = x1; x2 <= n; x2++ )
  47.                         if ( ( t = sum[ y2 ][ x2 ] - sum[ y0 ][ x2 ] - s ) > l )
  48.                             break;
  49.                         else
  50.                             if ( t >= k )
  51.                             {
  52.                                cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2; return 0;
  53.                             }
  54.  
  55.             }
  56.  
  57.     cout << no_solution; 
  58. }
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2
stdout
copy 
2 1 4 2
https://ideone.com/soOP5B
Plot Purchase
language:
C++14 (gcc 8.3)
created:
6 years 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!