結果
問題 | No.866 レベルKの正方形 |
ユーザー | TAISA_ |
提出日時 | 2019-08-16 23:06:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,822 bytes |
コンパイル時間 | 2,526 ms |
コンパイル使用メモリ | 169,036 KB |
実行使用メモリ | 415,048 KB |
最終ジャッジ日時 | 2023-10-24 04:17:25 |
合計ジャッジ時間 | 28,037 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,680 KB |
testcase_01 | AC | 3 ms
5,680 KB |
testcase_02 | AC | 2 ms
5,680 KB |
testcase_03 | AC | 2 ms
5,680 KB |
testcase_04 | AC | 2 ms
5,680 KB |
testcase_05 | AC | 2 ms
5,680 KB |
testcase_06 | AC | 3 ms
5,680 KB |
testcase_07 | AC | 2 ms
5,680 KB |
testcase_08 | AC | 1,693 ms
414,496 KB |
testcase_09 | AC | 1,805 ms
415,048 KB |
testcase_10 | AC | 2,000 ms
415,048 KB |
testcase_11 | AC | 2,026 ms
415,048 KB |
testcase_12 | AC | 1,622 ms
415,048 KB |
testcase_13 | AC | 2,002 ms
415,048 KB |
testcase_14 | AC | 1,522 ms
415,048 KB |
testcase_15 | AC | 2,033 ms
415,048 KB |
testcase_16 | AC | 1,889 ms
415,048 KB |
testcase_17 | AC | 2,005 ms
415,048 KB |
testcase_18 | AC | 2,002 ms
415,048 KB |
testcase_19 | AC | 1,433 ms
415,048 KB |
testcase_20 | AC | 1,298 ms
415,048 KB |
testcase_21 | WA | - |
testcase_22 | AC | 2 ms
5,680 KB |
testcase_23 | AC | 2 ms
5,680 KB |
testcase_24 | AC | 3 ms
7,732 KB |
ソースコード
#include <bits/stdc++.h> #define all(vec) vec.begin(), vec.end() using namespace std; using ll = long long; using P = pair<ll, ll>; constexpr ll INF = (1LL << 30) - 1LL; constexpr ll LINF = (1LL << 60) - 1LL; constexpr double eps = 1e-9; constexpr ll MOD = 1000000007LL; template <typename T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }; template <typename T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }; template <typename T> ostream &operator<<(ostream &os, vector<T> v) { for (int i = 0; i < v.size(); i++) { os << v[i] << (i + 1 == v.size() ? "\n" : " "); } return os; } template <typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; } template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for (auto &e : t) { fill_v(e, v); } }; int dat[1 << 12][1 << 12]; int co[1 << 11][1 << 11][26]; int h, w, k; int sum(int y1, int x1, int y2, int x2) { int res = 0; for (int k = 0; k < 26; k++) { if (co[y2][x2][k] - co[y1][x2][k] - co[y2][x1][k] + co[y1][x1][k] > 0) { res++; } } return res; } int calc(int p) { int res = 0; for (int i = 1; i < h; i++) { int y = i, x = 0; int l = 0; while (x < w && y < h) { while (l <= x && sum(i + l, l, y + 1, x + 1) >= p) { l++; } res += l; x++; y++; } } for (int i = 0; i < w; i++) { int y = 0, x = i; int l = 0; while (x < w && y < h) { while (l <= y && sum(l, i + l, y + 1, x + 1) >= p) { l++; } res += l; x++; y++; } } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> h >> w >> k; string s; for (int i = 0; i < h; i++) { cin >> s; for (int j = 0; j < w; j++) { co[i + 1][j + 1][s[j] - 'a']++; } } for (int i = 0; i <= h; i++) { for (int j = 1; j <= w; j++) { for (int k = 0; k < 26; k++) { co[i][j][k] += co[i][j - 1][k]; } } } for (int j = 0; j <= w; j++) { for (int i = 1; i <= h; i++) { for (int k = 0; k < 26; k++) { co[i][j][k] += co[i - 1][j][k]; } } } cout << calc(k) - calc(k + 1) << '\n'; }