結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー Kiona1018
提出日時 2019-09-12 21:09:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,638 bytes
コンパイル時間 1,694 ms
コンパイル使用メモリ 170,696 KB
実行使用メモリ 814,692 KB
最終ジャッジ日時 2024-07-02 17:10:09
合計ジャッジ時間 5,271 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;


int main()
{
    ll h, w, k;
    cin >> h >> w >> k;

    string table[h];
    rep(i, 0, h)
        cin >> table[i];

    ll cumsum[26][h+1][w+1];
    memset(cumsum, 0, sizeof(cumsum));

    rep(c, 0, 26)
    {
        char now = c + 'a';
        rep(i, 0, h)
            rep(j, 0, w)
            {
                cumsum[c][i+1][j+1] += cumsum[c][i+1][j] + cumsum[c][i][j+1];
                cumsum[c][i+1][j+1] -= cumsum[c][i][j];
                if (table[i][j] == now)
                    ++cumsum[c][i+1][j+1];
            }
    }
    // rep(i, 0, h)
    //     rep(j, 0, w)
    //         cout << i << ' ' << j << ' ' << cumsum[1][i+1][j+1] << endl;

    ll ans = 0;
    rep(i, 0, h)
        rep(j, 0, w)
        {
            // binary search for lower bound
            int l = 0;
            int r = min(h, w);
            while (l != r)
            {
                int mid = (l + r + 1) / 2;
                if (h < mid+i or w < mid+j)
                {
                    r = mid - 1;
                    continue;
                }

                int cnt = 0;
                rep(c, 0, 26)
                    cnt += int(
                        cumsum[c][i+mid][j+mid] 
                        - cumsum[c][i+mid][j] - cumsum[c][i][j+mid] 
                        + cumsum[c][i][j]> 0);
                if (cnt < k)
                    l = mid;
                else
                    r = mid - 1;
                // if (l == r)
                //     cout << i << ' ' << j << ' ' << l << ": " << cnt << endl;
            }
            int l_bottom = l;

            // binary search for upper bound
            r = min(h, w);
            l = 0;
            while (l != r)
            {
                int mid = (l + r + 1) / 2;
                if (h < mid+i or w < mid+j)
                {
                    r = mid - 1;
                    continue;
                }



                int cnt = 0;
                rep(c, 0, 26)
                    cnt += int(
                        cumsum[c][i+mid][j+mid] 
                        - cumsum[c][i+mid][j] - cumsum[c][i][j+mid] 
                        + cumsum[c][i][j]> 0);

                if (k < cnt)
                    r = mid - 1;
                else
                    l = mid;
            }
            ans += (ll) l - l_bottom;
            // cout << i << ' ' << j << ' ' << l << ' ' << l_bottom << ' ' << l - l_bottom << endl;
        }
    cout << ans << endl;
    return 0;
}
0