結果

問題 No.866 レベルKの正方形
ユーザー lumc_lumc_
提出日時 2019-08-17 05:42:28
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 5,155 ms / 6,000 ms
コード長 4,282 bytes
コンパイル時間 936 ms
コンパイル使用メモリ 105,280 KB
実行使用メモリ 413,956 KB
最終ジャッジ日時 2023-10-24 23:40:36
合計ジャッジ時間 62,613 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
38,872 KB
testcase_01 AC 10 ms
44,900 KB
testcase_02 AC 9 ms
38,872 KB
testcase_03 AC 11 ms
48,912 KB
testcase_04 AC 11 ms
48,916 KB
testcase_05 AC 10 ms
42,892 KB
testcase_06 AC 11 ms
42,892 KB
testcase_07 AC 9 ms
40,884 KB
testcase_08 AC 3,611 ms
413,952 KB
testcase_09 AC 4,010 ms
413,956 KB
testcase_10 AC 5,134 ms
413,956 KB
testcase_11 AC 5,073 ms
413,956 KB
testcase_12 AC 4,340 ms
413,956 KB
testcase_13 AC 5,053 ms
413,956 KB
testcase_14 AC 3,752 ms
413,956 KB
testcase_15 AC 5,030 ms
413,956 KB
testcase_16 AC 5,090 ms
413,956 KB
testcase_17 AC 5,086 ms
413,956 KB
testcase_18 AC 5,155 ms
413,956 KB
testcase_19 AC 3,441 ms
413,956 KB
testcase_20 AC 2,810 ms
413,956 KB
testcase_21 AC 2,609 ms
413,952 KB
testcase_22 AC 4 ms
16,268 KB
testcase_23 AC 5 ms
16,268 KB
testcase_24 AC 13 ms
57,084 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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