Submission #237114

#TimeUsernameProblemLanguageResultExecution timeMemory
237114DanShadersStrah (COCI18_strah)C++17
110 / 110
780 ms16120 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse,sse2,ssse3,sse4.1,sse4.2,avx,avx2") #include <bits/stdc++.h> #include <immintrin.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define all(x) begin(x), end(x) #define x first #define y second typedef long long ll; typedef long double ld; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<T>>; const int MAX_N = 2e3 + 10, INF = 0x3f3f; char a[MAX_N][MAX_N]; short b[MAX_N][MAX_N]; int last[MAX_N]; signed main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = n; i--; ) { for (int j = 0; j < m; ++j) { b[i][j] = b[i + 1][j] + 1; if (a[i][j] == '#') b[i][j] = 0; } } ll ans = 0; for (int i = 0; i < n; ++i) { last[m] = m; for (int j = m; j--; ) { last[j] = j + 1; while (last[j] < m && b[i][last[j]] >= b[i][j]) last[j] = last[last[j]]; } for (int j = 0; j < m; ++j) { int lef = j - 1; while (lef >= 0 && b[i][lef] > b[i][j]) --lef; int mult = 0; for (int h1 = lef + 1; h1 <= j; ++h1) for (int h2 = j; h2 < last[j]; ++h2) mult += h2 - h1 + 1; ans += ll(mult) * b[i][j] * (b[i][j] + 1) / 2; } } 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...