Submission #1013813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013813		May27_th	Bob (COCI14_bob)	C++17	0 / 120	83 ms	16260 KiB

bob

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests;
  while (Tests --) {
    int N, M; cin >> N >> M;
    vector<vector<int>> a(N + 2, vector<int> (M + 2, 0));
    vector<vector<int>> h(N + 2, vector<int> (M + 2, 0));
    vector<vector<i64>> f(N + 2, vector<i64> (M + 2, 0));
    for (int i = 1; i <= N; i ++) {
      for (int j = 1; j <= M; j ++) {
        cin >> a[i][j];
      }
    }
    for (int j = 1; j <= M; j ++) {
      for (int i = 1; i <= N; i ++) {
        if (a[i][j] != a[i - 1][j]) h[i][j] = 1;
        else h[i][j] = h[i - 1][j] + 1;
      }
    }
    i64 ans = 0;
    stack<int> st;
    for (int i = 1; i <= N; i ++) {
      while (!st.empty()) st.pop();
      for (int j = 1; j <= M; j ++) {
        if (a[i][j] != a[i][j - 1]) {
          while (!st.empty()) st.pop();
          f[i][j] = h[i][j];
          ans += f[i][j];
          h[i][j - 1] = 0;
          f[i][j - 1] = 0;
          st.push(j - 1);
          continue;
        }
        while (!st.empty() && h[i][st.top()] >= h[i][j]) st.pop();
        f[i][j] = f[i][st.top()] + (j - st.top()) * h[i][j];
        ans = ans + f[i][j];
        st.push(j);
      }
    }
    for (int i = 1; i <= N; i ++) {
      for (int j = 1; j <= M; j ++) {
        // cout << f[i][j] << " ";
        // ans = ans + f[i][j]; 
      } // cout << "\n";
    }
    cout << ans << "\n";
  }
}

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