Submission #384684

#TimeUsernameProblemLanguageResultExecution timeMemory
384684AdiZer0Strah (COCI18_strah)C++17
110 / 110
358 ms71276 KiB
#include <bits/stdc++.h> #define pb push_back #define whole(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; typedef long long ll; typedef long double ld; const int N = (int)2005 + 7; const int INF = (int)1e9 + 7; const ll linf = (ll)1e18 + 1; int n, m; char a[N][N]; ll sumW[N][N], sumH[N][N], pref[N]; ll get(ll x) { ll res = (x * (x + 1)) / 2; return res; } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; } } ll ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (a[i][j] == '.') ++pref[j]; else pref[j] = 0; } stack<int> st; for (int j = 1; j <= m; ++j) { while (!st.empty() && pref[st.top()] >= pref[j]) st.pop(); int pos = 0; if (!st.empty()) pos = st.top(); int width = j - pos, height = pref[j]; sumW[i][j] += sumW[i][pos] + sumH[i][pos] * 1ll * width; sumH[i][j] += sumH[i][pos] + get(height) * 1ll * width; sumW[i][j] += get(width) * 1ll * get(height); ans += sumW[i][j]; st.push(j); } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...