fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <stack>
  11. #include <queue>
  12. #include <algorithm>
  13. #include <cassert>
  14. #include <random>
  15. #include <chrono>
  16. #include <iomanip>
  17. #include <cmath>
  18. #include <bitset>
  19. #define int long long
  20. #define double long double
  21. #define ii pair<int,int>
  22. #define iii pair<int, ii >
  23. #define fi first
  24. #define se second
  25. #define getbit(x,y) (((x)>>(y))&1)
  26. #define turnon(x,y) ((x)|(1ll<<y))
  27. #define turnof(x,y) ((x)^(1ll<<y))
  28. #define oo 1e18
  29. #define pb push_back
  30. #define all(x) x.begin(),x.end()
  31. #define con(mask) mask=(mask-1)&mask
  32. #define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())
  33.  
  34. #define rand_int mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  35. #define rand_ll mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  36.  
  37. const int mod = 1e9 + 7;
  38. const int base = 448;
  39. using namespace std;
  40.  
  41. int n, m, k;
  42.  
  43. int h[505][505];
  44.  
  45. int get(int x, int y, int u, int v) {
  46.     return h[u][v] - h[x - 1][v] - h[u][y - 1] + h[x - 1][y - 1];
  47. }
  48.  
  49.  
  50. signed main() {
  51.  
  52.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  53.  
  54.     cin >> n >> m >> k;
  55.  
  56.     for(int i = 1; i <= n; i++) {
  57.         for(int j = 1; j <= m; j++) {
  58.             cin >> h[i][j];
  59.             h[i][j] += h[i][j - 1] + h[i - 1][j] - h[i - 1][j - 1];
  60.         }
  61.     }
  62.  
  63.     if(h[n][m] < k) {
  64.         cout << -1;
  65.         return 0;
  66.     }
  67.  
  68.     int res = n * m;
  69.     int x, y, u, v;
  70.  
  71.     for(int a = 1; a <= n; a++) {
  72.         for(int b = a; b <= n; b++) {
  73.             int pos = 1;
  74.  
  75.             for(int i = 1; i <= m; i++) {
  76.                 while(get(a, pos + 1, b, i) >= k)pos++;
  77.  
  78.                 if(get(a, pos, b, i) >= k) {
  79.                     int dt = (b - a + 1) * (i - pos + 1);
  80.  
  81.                     if(dt < res) {
  82.                         res = dt;
  83.                         x = a;
  84.                         y = pos;
  85.                         u = b;
  86.                         v = i;
  87.                     }
  88.                 }
  89.             }
  90.         }
  91.     }
  92.  
  93.  
  94.     cout << res << "\n";
  95.     cout << x << " " << y << " " << u << " " << v;
  96. }
  97.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
22969470678945 94549520863240 94549522904064 1
https://ideone.com/du3SlC
language:
C++14 (gcc 8.3)
created:
16 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!