結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー lumc_
提出日時 2019-08-17 05:42:28
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 5,282 ms / 6,000 ms
コード長 4,282 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 945 ms
コンパイル使用メモリ 104,796 KB
実行使用メモリ 413,804 KB
最終ジャッジ日時 2024-09-24 18:43:27
合計ジャッジ時間 61,083 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// accum2D range2D range2Dloop {{{
#include <type_traits>
using loop2d_int = long long;
template < class T >
void accum2D(T &val, int h, int w) {
  for(int i = 1; i < h; i++)
    for(int j = 0; j < w; j++) val[i][j] += val[i - 1][j];
  for(int i = 0; i < h; i++)
    for(int j = 1; j < w; j++) val[i][j] += val[i][j - 1];
}

template < class T >
         auto range2D(T &val, int y1, int x1, int y2, int x2, int h, int w) {
           using V = typename std::remove_reference<decltype(val[0][0])>::type;
           if(y2 >= h) y2 = h - 1;
           if(x2 >= w) x2 = w - 1;
           if(y1 > y2 || x1 > x2) return static_cast< V >(0);
           V res(val[y2][x2]);
           if(y1 - 1 >= 0) res -= val[y1 - 1][x2];
           if(x1 - 1 >= 0) res -= val[y2][x1 - 1];
           if(y1 - 1 >= 0 && x1 - 1 >= 0) res += val[y1 - 1][x1 - 1];
           return res;
         }

template < class T,
         class V = typename std::remove_reference< decltype(T()[0][0]) >::type >
         auto range2Dloop(T &val, loop2d_int ty1, loop2d_int tx1, loop2d_int y2, loop2d_int x2,
             int h, int w) {
           if(ty1 > y2 || tx1 > x2) return static_cast< V >(0);

           loop2d_int y1 = ty1 % h;
           if(y1 < 0) y1 += h;
           loop2d_int x1 = tx1 % w;
           if(x1 < 0) x1 += w;

           y2 += y1 - ty1;
           x2 += x1 - tx1;

           loop2d_int gy = y2 / h;
           loop2d_int gx = x2 / w;
           y2 %= h;
           x2 %= w;

           V res(0);
           if(gy == 0 && gx == 0) {
             res += range2D< T >(val, y1, x1, y2, x2, h, w);
           } else if(gy == 0) {
             res += range2D< T >(val, y1, x1, y2, w - 1, h, w);
             res += range2D< T >(val, y1, 0, y2, x2, h, w);
             res += range2D< T >(val, y1, 0, y2, w - 1, h, w) * (gx - 1);
           } else if(gx == 0) {
             res += range2D< T >(val, y1, x1, h - 1, x2, h, w);
             res += range2D< T >(val, 0, x1, y2, x2, h, w);
             res += range2D< T >(val, 0, x1, h - 1, x2, h, w) * (gy - 1);
           } else {
             res += range2D< T >(val, y1, x1, h - 1, w - 1, h, w);                     // UL
             res += range2D< T >(val, 0, x1, y2, w - 1, h, w);                         // DL
             res += range2D< T >(val, y1, 0, h - 1, x2, h, w);                         // UR
             res += range2D< T >(val, 0, 0, y2, x2, h, w);                             // DR
             res += range2D< T >(val, y1, 0, h - 1, w - 1, h, w) * (gx - 1);           // U
             res += range2D< T >(val, 0, 0, y2, w - 1, h, w) * (gx - 1);               // D
             res += range2D< T >(val, 0, x1, h - 1, w - 1, h, w) * (gy - 1);           // L
             res += range2D< T >(val, 0, x1, h - 1, x2, h, w) * (gy - 1);              // R
             res += range2D< T >(val, 0, 0, h - 1, w - 1, h, w) * (gy - 1) * (gx - 1); // C
           }
           return res;
         }
// }}}

int h, w, k;
string f[2000];

int g[26][2000][2000];

int cnt(int y1, int x1, int y2, int x2) {
  int res = 0;
  for(int c = 0; c < 26; c++) res += !!range2D(g[c], y1, x1, y2, x2, h, w);
  return res;
}

// レベルp以上 の物の数を求める
ll solve(int p) {
  if(k == 27) return 0;
  // 1 - w <= u = y - x <= h - 1
  ll res = 0;
  for(int u = 1 - w; u <= h - 1; u++) {
    // x = y - u
    int c = 0;
    int v = -1;
    for(int y = max(0, 0 + u); y <= min(h - 1, w - 1 + u); y++, v--) {
      int x = y - u;
      while(v + 1 <= 0 and cnt(y + v + 1, x + v + 1, y, x) >= p) v++, c++;
      res += c;
    }
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> h >> w >> k;
  for(int i = 0; i < h; i++) {
    cin >> f[i];
    for(int j = 0; j < w; j++) g[f[i][j]-'a'][i][j]++;
  }
  for(int c = 0; c < 26; c++) accum2D(g[c], h, w);
  cout << solve(k) - solve(k + 1) << endl;
  return 0;
}
0