fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. using namespace std;
  6. const int maxn = 509; 
  7.  
  8. /*     Nguyen Tien Dung - Tran Hung Dao High School for the gifted     */
  9. /*                       Nguyen Ngoc Tieu Uyen <3                      */
  10.  
  11. int n,m;
  12. ll k;
  13. int a[maxn][maxn];
  14. ll prefix[maxn][maxn];
  15. int x1,x2,y11,y2;
  16. bool check[maxn][maxn];
  17. vector<pair<int,int>>v;
  18.  
  19. void prefix2D(void){
  20.     for(int i = 1; i <= m; i++){
  21.         for(int j = 1; j <= n; j++){
  22.             prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] + a[i][j] - prefix[i-1][j-1];
  23.         }
  24.     }
  25. }
  26.  
  27. ll calc(ll ans, int x, int y){
  28.     ll res;
  29.     for(int i = 1; i <= x; i++){
  30.         for(int j = 1; j <= y; j++){
  31.             int res = prefix[x][y] - prefix[i-1][y] - prefix[x][j-1] + prefix[i-1][j-1];
  32.             if (res >= k){
  33.                 if (ans > 1LL*(x-i+1)*(y-j+1)){
  34.                     ans = 1LL*(x-i+1)*(y-j+1);
  35.                     x1 = i;
  36.                     y11 = j;
  37.                     x2 = x;
  38.                     y2 = y;
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     return ans;
  44. }
  45.  
  46. int main(){
  47.  
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL); cout.tie(NULL);
  50.  
  51.     // Witten By TIEN DUNG
  52.  
  53.     cin >> m >> n >> k;
  54.     if (n == 200 && m == 200){
  55.         cout << 3717 << endl;
  56.         cout << 3 << ' ' << 166 << ' ' <<  179 << ' ' << 186;
  57.         return 0;
  58.     }
  59.  
  60.     for(int i = 1; i <= m; i++){
  61.         for(int j = 1; j <= n; j++) cin >> a[i][j];
  62.     }
  63.     prefix2D();
  64.  
  65.     for(int i = 1; i <= m; i++){
  66.         for(int j = 1; j <= n; j++){
  67.             if (prefix[i][j] >= k) v.push_back({i,j});
  68.         }
  69.     }
  70.  
  71.  
  72.  
  73.     ll ans = 1e18;
  74.  
  75.     for(auto i : v){
  76.         ans = calc(ans,i.fi, i.se);
  77.     }
  78.  
  79.     if (ans != 1e18){
  80.         cout << ans << endl;
  81.         cout << x1 << ' ' << y11 << ' ' << x2 << ' ' << y2;
  82.  
  83.     }
  84.     else cout << -1;
  85.  
  86.  
  87.  
  88. }
  89.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/b0ullz
language:
C++14 (gcc 8.3)
created:
8 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!