This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// NK
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)
const int MAXS = 2010;
char ma[MAXS][MAXS];
ll triacc[MAXS], tri[MAXS];
int helper[MAXS];
int n,m;
ll f(ll x){
return x*(x+1) / 2ll;
}
void solve(){
cin>>n>>m;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
cin>>ma[i][j];
for (ll i=1; i<MAXS; i++) triacc[i] = triacc[i-1] + i*(i+1) / 2ll, tri[i] = tri[i-1] + i;
ll ans = 0;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
if (ma[i][j] == '.'){
helper[j]++;
}else helper[j] = 0;
}
stack<pair<int,ll>> st; // elem, counter
st.push(mkp(0,0));
for (int j=1; j<=m; j++){
//cout<<helper[j];
ll aux = 0;
while (st.top().first > helper[j]){
aux = st.top().second;
int h = st.top().first;
st.pop();
int bh = st.top().first;
ll diff = tri[h];
int maxi = max(bh, helper[j]);
diff -= tri[maxi];
ll tmp = diff * (triacc[aux]);
ans = ans + tmp;
st.top().second += aux;
}
if (st.top().first < helper[j]){
st.top().second -= aux;
st.push(mkp(helper[j], aux+1));
}else{
st.top().second++;
}
}
//pop all:
ll aux = 0;
while(st.top().first > 0){
aux = st.top().second;
int h = st.top().first;
st.pop();
int bh = st.top().first;
ll diff = tri[h];
int maxi = bh;
diff -= tri[maxi];
ll tmp = diff * (triacc[aux]);
ans = ans + tmp;
st.top().second += aux;
}
//cout<<'\n';
}
cout<<ans<<'\n';
}
int main(){
Bolivia_is_nice;
int t = 1; //cin>>t;
while(t--)
solve();
return 0;
}
/*
~/.emacs
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |