Submission #1266059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266059		canhnam357	Bob (COCI14_bob)	C++20	120 / 120	65 ms	8264 KiB

bob

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;   
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &x : a) for (int &i : x) cin >> i;
    vector<vector<int>> g(n, vector<int>(m, 1));
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == a[i - 1][j]) g[i][j] = g[i - 1][j] + 1;
        }
    }   
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        stack<tuple<int, int, int>> s;
        long long sum = 0;
        int p = 0;
        for (int j = 0; j < m; j++) {
            if (j && a[i][j] != a[i][j - 1]) {
                while (!s.empty()) s.pop();
                sum = g[i][j];
                s.emplace(g[i][j], j, 1);
                p = j;
            }
            else {
                while (!s.empty() && get<0>(s.top()) >= g[i][j]) {
                    auto [x, y, z] = s.top();
                    s.pop();
                    sum -= x * z;
                }
                if (s.empty()) {
                    s.emplace(g[i][j], p, j - p + 1);
                    sum += g[i][j] * (j - p + 1);
                }
                else {
                    int t = get<1>(s.top()) + get<2>(s.top()) - 1;
                    s.emplace(g[i][j], t + 1, j - t);
                    sum += g[i][j] * (j - t);
                }
            }
            ans += sum;
        }
    }
    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