제출 #397422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397422		mewnian	Bob (COCI14_bob)	C++14	120 / 120	185 ms	41540 KiB

bob

#include <bits/stdc++.h>
#define sze(x) (ll)x.size()
#define idx(x, a) get<x>(a)
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;

const ll MAXN = 1e3 + 3;
const ll INF = 1e18 + 7;

ll a[MAXN][MAXN], h[MAXN][MAXN], l[MAXN][MAXN], cnt[MAXN][MAXN], m, n, res = 0;

int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
    #ifdef OFFLINE
    freopen("input.inp", "r", stdin);
    #endif
    cin >> m >> n;
    for (ll i = 1; i <= m; ++i)
    {
        for (ll j = 1; j <= n; ++j) cin >> a[i][j];
        h[i][0] = h[i][n + 1] = -INF;
    }
    fill(h[1] + 1, h[1] + n + 1, 1);
    for (ll i = 2; i <= m; ++i)
        for (ll j = 1; j <= n; ++j)
            h[i][j] = (a[i][j] == a[i - 1][j] ? h[i - 1][j] + 1 : 1);
    vector<ll> posL;
    for (ll i = 1; i <= m; ++i)
    {
    	posL.clear();
        for (ll j = 1; j <= n; ++j)
        {
            if (j == 1 || a[i][j] != a[i][j - 1]) posL = {j - 1};
            else
            while (a[i][j] == a[i][posL.back()] && h[i][j] <= h[i][posL.back()])
            {
                //cnt[i][j] += (j - posL.back()) * h[i][j];
                posL.pop_back();
            }
            l[i][j] = posL.back();
            posL.push_back(j);
            cnt[i][j] += (j - l[i][j]) * h[i][j];
            if (a[i][l[i][j]] == a[i][j]) cnt[i][j] += cnt[i][l[i][j]];
            //cerr << cnt[i][j] << ' ';
            res += cnt[i][j];
        }
        //cerr << endl;
    }
    cout << res;
}

• 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