fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define N 101
  5. int a[N][N], b[N][N];
  6.  
  7. int main() {
  8.   /* Enter your code here. Read input from STDIN. Print output to STDOUT */
  9.   ios_base::sync_with_stdio(0);
  10.   int n, m;
  11.   cin >> n >> m;
  12.   for(int i = 1; i <= n; i++) {
  13.     for(int j = 1; j <= m; j++) {
  14.       cin >> b[i][j];
  15.       a[i][j] = b[i][j];
  16.       a[i][j] += a[i - 1][j];
  17.       a[i][j] += a[i][j - 1];
  18.       a[i][j] -= a[i - 1][j - 1];
  19.     }
  20.   }
  21.   int p, A;
  22.   cin >> A >> p;
  23.   for(int ca = n * m; ca >= A; ca--) {
  24.     vector<int> l, g;
  25.     //cout<<a<<endl;
  26.     for(int i = 1; i * i <= ca; i++) {
  27.       if((ca % i) == 0) {
  28.         l.emplace_back(i);
  29.         if(i * i != ca) {
  30.           g.emplace_back(ca / i);
  31.         }
  32.       }
  33.     }
  34.     for(int i = (int)g.size() - 1; i >= 0; i--) {
  35.       l.emplace_back(g[i]);
  36.     }
  37.     vector<int> w;
  38.     for(int i = 0; i < l.size(); i++) {
  39.       w.emplace_back(ca / l[i]);
  40.     }
  41.     int r = l.size();
  42.     int p1 = 0, p2 = r - 1;
  43.     for(int i = 1; i <= n; i++) {
  44.       while(p2 >= 0 && i + l[p2] - 1 > n) {
  45.         p2--;
  46.       }
  47.       p1 = 0;
  48.       for(int j = 1; j <= m; j++) {
  49.         while(p1 < r && j + w[p1] - 1 > m) {
  50.           p1++;
  51.         }
  52.         //cout << "1: " << i << " " << j << " " << p1 << " " << p2 << endl;
  53.         for(int k = p1; k <= p2; k++) {
  54.           int c = i + l[k] - 1;
  55.           int d = j + w[k] - 1;
  56.           int cur = a[c][d] - a[i - 1][d] - a[c][j - 1] + a[i - 1][j - 1];
  57.           if((cur * 100) / ca >= p) {
  58.             cout << i << " " << j << " " << c << " " << d << '\n';
  59.             for(int ii = i; ii <= c; ii++) {
  60.               for(int jj = j; jj <= d; jj++) {
  61.                 b[ii][jj] = -10001;
  62.               }
  63.             }
  64.             for(int ii = 1; ii <= n; ii++) {
  65.               for(int jj = 1; jj <= m; jj++) {
  66.                 a[ii][jj] = b[ii][jj];
  67.                 a[ii][jj] += a[ii - 1][jj];
  68.                 a[ii][jj] += a[ii][jj - 1];
  69.                 a[ii][jj] -= a[ii - 1][jj - 1];
  70.               }
  71.             }
  72.           }
  73.         }
  74.       }
  75.     }
  76.   }
  77.   return 0;
  78. }
  79.  
Runtime error #stdin #stdout 0s 3548KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/w3J7Lk
language:
C++14 (gcc 8.3)
created:
8 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!