fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ll long long
  5. #define pii pair<ll,ll>
  6. #define vi vector<ll>
  7. #define vb vector<bool>
  8. #define vvi vector<vi>
  9. #define vpii vector<pii>
  10. #define vvpii vector<vpii>
  11. #define F first
  12. #define S second
  13. #define pb push_back
  14. #define all(v) v.begin(),v.end()
  15. #define fr(i, begin, end) for (__typeof(begin) i = (begin); i != (end) + ((begin) > (end) ? -1 : 1); (begin) > (end) ? i-- : i++)
  16. #define rep(i,n) for(ll i=0; i<n; i++)
  17. #define ret(msg) {cout << msg << endl; return;}
  18. #define prt(a) cout << a << endl;
  19. #define prt1(a) cout << a << " ";
  20. #define prt2(a,b) cout << a << " " << b << endl;
  21. #define popcnt(x) __builtin_popcountll(x)
  22. #define uniq(s) s.erase(unique(s.begin(),s.end()),s.end())
  23. #define mod 1000000007
  24. #define MOD 998244353
  25. #define double long double
  26.  
  27. void solve(){
  28.     ll n, m;
  29.     cin >> n >> m;
  30.     vector<string> v(n);
  31.     rep(i, n)cin >> v[i];
  32.     bool rot = false;
  33.     if(n > m){
  34.         vector<string> v1(m);
  35.         rep(j, m){
  36.             string tmp = "";
  37.             rep(i, n){
  38.                 tmp.pb(v[i][j]);
  39.             }
  40.             v1[j] = tmp;
  41.         }
  42.         v = v1;
  43.         rot = true;
  44.         swap(n, m);
  45.     }
  46.     vvi ans(n, vi(m, 1e9));
  47.     for(int i = 0; i < n; i++)
  48.     {
  49.         vvi tmp(n, vi(m, 1e9));
  50.  
  51.         for(ll j = n - 1; j > i; j--)
  52.         {
  53.             ll col = -1;
  54.             for(ll k = 0; k < m; k++)
  55.             {
  56.                 if(v[i][k] == '1' && v[j][k] == '1')
  57.                 {
  58.                     if(col == -1)
  59.                     {
  60.                         col = k;
  61.                     }
  62.                     else
  63.                     {
  64.                         ll area = (j - i + 1)*(k - col + 1);
  65.                         for(ll k1 = col; k1 <= k; k1++)
  66.                         {
  67.                             tmp[j][k1] = min(tmp[j][k1], area);
  68.                             // cols[k1].pb({i, j, area});
  69.                         }
  70.                         col = k;
  71.                     }
  72.                 }
  73.             }
  74.  
  75.         }
  76.  
  77.         for(ll j = n - 1; j >= i; j--)
  78.         {
  79.             for(ll k = 0; k < m; k++)
  80.             {
  81.                 if(j + 1 < n) tmp[j][k] = min(tmp[j][k], tmp[j + 1][k]);
  82.                 ans[j][k] = min(ans[j][k], tmp[j][k]);
  83.             }
  84.         }
  85.  
  86.     }
  87.     // vvi dp(n, vi(n, 1e9));
  88.     // rep(i, m){
  89.     //     for(auto a : cols[i]){
  90.     //         dp[a[0]][a[1]] = min(dp[a[0]][a[1]], a[2]);
  91.     //     }
  92.     //     // rep(j, n){
  93.     //     //     rep(k, n)prt1(dp[j][k]);
  94.     //     //     cout << endl;
  95.     //     // }
  96.     //     for(ll len = n; len >= 1; len--){
  97.     //         for(ll j = 0; j + len - 1 < n;j++){
  98.     //             if(j > 0)dp[j][j + len - 1] = min(dp[j][j + len - 1], dp[j - 1][j + len - 1]);
  99.     //             if(j + len - 1 < n - 1)dp[j][j + len - 1] = min(dp[j][j + len - 1], dp[j][j + len]);
  100.     //         }
  101.     //     }
  102.     //     rep(j, n)ans[j][i] = dp[j][j];
  103.     //     rep(j, n)rep(k, n)dp[j][k] = 1e9;
  104.     // }
  105.     if(rot){
  106.         rep(j, m){
  107.             rep(i, n)cout << (ans[i][j] == 1e9 ? 0 : ans[i][j]) << " ";
  108.             cout << endl;
  109.         }
  110.         return;
  111.     }
  112.     rep(i, n){
  113.         rep(j, m)cout << (ans[i][j] == 1e9 ? 0 : ans[i][j]) << " ";
  114.         cout << endl;
  115.     }
  116. }
  117.  
  118. int32_t main() {
  119.     //doo();
  120.     // SOE(N);
  121.     // SOE1(N);
  122.     // pre();
  123.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  124.     int t=1;
  125.     cin >> t;
  126.     // if(t == 2955){
  127.     //     while(t--){
  128.     //         ll n, m, k;
  129.     //         cin >> n >> m >> k;
  130.     //         if(t == 2955 - 37)cout << n << " " << m << " " << k << endl;
  131.     //     }
  132.     // }else{
  133.     while(t--) {
  134.         solve();
  135.     }
  136.     // }
  137. }
Runtime error #stdin #stdout #stderr 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/3p56tN
language:
C++14 (gcc 8.3)
created:
108 days ago
visibility:
secret

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!