Submission #679723

#	Time	Username	Problem	Language	Result	Execution time	Memory
679723		vjudge1	Bob (COCI14_bob)	C++14	120 / 120	115 ms	13948 KiB

bob

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

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int m, n;
ll res = 0;

void solve()
{
    cin >> n >> m;
    int a[n + 1][m + 1], h[m + 1]{}, l[m + 1]{};
    ll dp[m + 1]{};
    memset(a, 0, sizeof a);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            h[j]++;
            if(a[i][j] != a[i - 1][j]) h[j] = 1;
        }
        stack<int> s;
        for(int j = 1; j <= m; j++)
        {
            while(s.size() && a[i][j] == a[i][s.top()] && h[j] <= h[s.top()]) s.pop();
            if(s.empty()) l[j] = 0;
            else l[j] = s.top();
            s.push(j);
        }
        for(int j = 1; j <= m; j++)
        {
            dp[j] = 1LL * (j - l[j]) * h[j];
            if(a[i][j] == a[i][l[j]]) dp[j] += dp[l[j]];
            res += dp[j];
        }
    }
    cout << res;   
}

signed main()
{
    cin.tie(0)->sync_with_stdio(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