Submission #199522

#TimeUsernameProblemLanguageResultExecution timeMemory
199522ZwariowanyMarcinStrah (COCI18_strah)C++14
110 / 110
196 ms20104 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define ss(x) (int) x.size() #define pb push_back #define LL long long #define LD long double #define cat(x) cerr << #x << " = " << x << endl #define FOR(i, j, n) for(int i = j; i <= n; ++i) #define boost cin.tie(0), ios_base::sync_with_stdio(0); using namespace std; const int nax = 2011; int n, m; char s[nax][nax]; int up[nax][nax]; LL ans; LL tyt[nax]; LL f(int x) { return (LL) x * (x + 1) / 2; } int L[nax]; int R[nax]; vector <int> v; int main() { scanf ("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { scanf ("%s", s[i] + 1); for (int j = 1; j <= m; ++j) { if (s[i][j] == '#') up[i][j] = 0; else up[i][j] = up[i - 1][j] + 1; } } for (int i = 1; i <= m; ++i) { LL res = 0; for (int j = 1; j <= i; ++j) res += j * (i - j + 1); tyt[i] = res; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m + 1; ++j) { while (ss(v) && up[i][v.back()] > up[i][j]) { R[v.back()] = j - 1; v.pop_back(); } if (j != m + 1) v.pb(j); } for (int j = m; 0 <= j; --j) { while (ss(v) && up[i][v.back()] >= up[i][j]) { L[v.back()] = j + 1; v.pop_back(); } if (j != 0) v.pb(j); } for (int j = 1; j <= m; ++j) { if (!up[i][j]) continue; int h = max(up[i][L[j] - 1], up[i][R[j] + 1]); LL gao = (LL) (f(up[i][j]) - f(h)) * tyt[R[j] - L[j] + 1]; ans += gao; } } printf ("%lld", ans); return 0; }

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~~
strah.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s", s[i] + 1);
   ~~~~~~^~~~~~~~~~~~~~~~
#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...