Submission #1013810

# Submission time Handle Problem Language Result Execution time Memory
1013810 2024-07-04T06:20:02 Z May27_th Bob (COCI14_bob) C++17
0 / 120
88 ms 25940 KB
#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];
          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";
  }
}
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 5336 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 5468 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5464 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 22864 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 25940 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 25680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 25936 KB Output isn't correct
2 Halted 0 ms 0 KB -