Submission #1045737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045737		NeroZein	Strah (COCI18_strah)	C++17	110 / 110	79 ms	23756 KiB

strah

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 2003;

char c[N][N];
int down[N][N];

int sum(int l, int r) {
  return r * (r + 1) / 2 - l * (l - 1) / 2; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> c[i][j]; 
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= m; ++j) {
      if (c[i][j] == '#') {
        down[i][j] = i;
      } else {
        down[i][j] = (i == n ? n + 1 : down[i + 1][j]); 
      }
    }
  }
  long long ans = 0; 
  for (int i = 1; i <= n; ++i) {
    long long sumv = 0; 
    long long in_stack = 0; 
    vector<array<int, 3>> stk; 
    for (int j = m; j >= 1; --j) {
      int nr = j; 
      while (!stk.empty()) {
        auto [l, r, v] = stk.back();
        if (v <= (down[i][j] - i)) {
          break;
        } else {
          sumv -= (long long) (r - l + 1) * v * (v + 1) / 2;
          in_stack -= (long long) sum(l, r) * v * (v + 1) / 2;
          nr = r; 
          stk.pop_back(); 
        }
      }
      int v = (down[i][j] - i); 
      sumv += (long long) (nr - j + 1) * v * (v + 1) / 2; 
      in_stack += (long long) sum(j, nr) * v * (v + 1) / 2; 
      stk.push_back({j, nr, v});
      long long res = in_stack;
      res -= (long long) (j - 1) * sumv;
      ans += res; 
    }
  }
  cout << ans << '\n'; 
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11