fork download
copy 
  1. using namespace std;
  2. #include<bits/stdc++.h>
  3.  
  4. #define BG begin()
  5. #define ED end()
  6. #define st first
  7. #define nd second
  8. #define PB push_back
  9. #define PF push_front
  10. #define FOR(i,a,b) for (long long i=a;i<b;i++)
  11. #define FORE(i,a,b) for (long long i=a;i<=b;i++)
  12. #define FORD(i,a,b) for (long long i=a;i>=b; i--)
  13. #define ri(n)({\
  14.     int neg=0;\
  15.     n=0;\
  16.     char ch;\
  17.     for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;\
  18.     n=ch-48;\
  19.     for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;\
  20.     if (neg) n=-n;\
  21. })
  22.  
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef pair<int,int> II;
  26. typedef pair<ll,ll> LL;
  27. const ll INF=1000000000+7;
  28. const double esp=1e-13;
  29. const double pi=3.141592653589;
  30.  
  31.  
  32. ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];
  33.  
  34. int main()
  35. {
  36.     //freopen("CREC01.inp", "r", stdin);
  37.     //freopen("CREC01.out", "w", stdout);
  38.     cin>>m>>n;
  39.     char ch;
  40.     FORE(i, 1, m)
  41.         FORE(j, 1, n) {
  42.             cin>>ch;
  43.             a[i][j] = ch - '0';
  44.         }
  45.     memset(H, 0, sizeof(H));
  46.     memset(L, 0, sizeof(L));
  47.     memset(dem, 0, sizeof(dem));
  48.     long long ans = 0;
  49.     FORE(i, 1, m)
  50.         FORE(j, 1, n) {
  51.             //cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
  52.             if (a[i][j] == 1) {
  53.                 H[j]++;
  54.                 int k = j;
  55.                 while ( (k > 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
  56.                 L[j] = k;
  57.                 dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
  58.                 ans += dem[j];
  59.                 //cout<<i<<"=="<<j<<"=="<<"=="<<H[j]<<"=="<<ans<<endl;
  60.             }
  61.             else
  62.             {
  63.                 H[j] = 0;
  64.                 dem[j]= 0;
  65.                 L[j] = 0;
  66.             }
  67.         }
  68.     cout<<ans;
  69. }
Success #stdin #stdout 0s 23088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/S0t4zZ
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!