oj.uz

Submission #1013813

# Submission time Handle Problem Language Result Execution time Memory
1013813 2024-07-04T06:24:46 Z May27_th Bob (COCI14_bob) C++17
0 / 120
 83 ms 16260 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];
          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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 4404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 16216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 16220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 16260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 16220 KB Output isn't correct
2 Halted 0 ms 0 KB -