Submission #1146679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146679		THXuan	Bob (COCI14_bob)	C++20	120 / 120	67 ms	15980 KiB

bob

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <set>
#define INF 1e9
using namespace std;
typedef long long ll;

ll v[1005][1005], dp[1005][1005];

void solve()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> v[i][j];
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = i;
            if (v[i + 1][j] == v[i][j])dp[i][j] = max(dp[i][j], dp[i + 1][j]);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        stack<pair<ll, ll>>stk;
        ll color = -1;
        ll counter = 0;
        for (int j = m; j >= 1; j--) {
            if (v[i][j] != color) {
                while (!stk.empty()) stk.pop();
                counter = 0;
            }
            color = v[i][j];
            ll cnt = 1;
            ll dep = dp[i][j] - i + 1;
            while (!stk.empty() && stk.top().first >= dep) {
                cnt += stk.top().second;
                counter -= stk.top().first * stk.top().second;
                stk.pop();
            }
            stk.push({dep ,cnt});
            counter += dep * cnt;
            ans += counter;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;//cin >> t;
    while (t--) solve();
    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