Submission #697160

#	Time	Username	Problem	Language	Result	Execution time	Memory
697160		kusssso	Bob (COCI14_bob)	C++17	120 / 120	121 ms	8988 KiB

bob

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1005;

int n, m;
int a[N][N];
ll ans;

signed main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cin >> n >> m;
      for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) cin >> a[i][j];
      }
      vector<int> h(m + 1, 0);
      for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) h[j] = (a[i][j] == a[i - 1][j] ? h[j] + 1 : 1);
            // for (int j = 1; j <= m; j++) cout << h[j] << ' ';
            // cout << '\n';
            // continue;
            vector<int> l(m + 1, 0);
            vector<int> r(m + 1, 0);
            deque<int> d;
            for (int j = 1; j <= m; j++) {
                  int t;
                  for (t = j; t <= m && a[i][t] == a[i][j]; t++) {
                        while (!d.empty() && h[t] <= h[d.back()]) d.pop_back();
                        l[t] = (d.empty() ? j : d.back() + 1);
                        d.push_back(t);
                  }
                  j = t - 1;
                  d.clear();
            }
            for (int j = m; j >= 1; j--) {
                  int t;
                  for (t = j; t >= 1 && a[i][t] == a[i][j]; t--) {
                        while (!d.empty() && h[t] < h[d.back()]) d.pop_back();
                        r[t] = (d.empty() ? j : d.back() - 1);
                        d.push_back(t);
                  }
                  j = t + 1;
                  d.clear();
            }
            for (int j = 1; j <= m; j++) {
                  ans += 1LL * (j - l[j] + 1) * (r[j] - j + 1) * h[j];
            }
      }
      cout << ans;
      return 0;
}

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