結果
問題 | No.866 レベルKの正方形 |
ユーザー | ok |
提出日時 | 2021-11-17 12:16:05 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4,067 ms / 6,000 ms |
コード長 | 1,759 bytes |
コンパイル時間 | 948 ms |
コンパイル使用メモリ | 86,364 KB |
実行使用メモリ | 415,168 KB |
最終ジャッジ日時 | 2023-08-24 22:56:48 |
合計ジャッジ時間 | 53,579 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,528 KB |
testcase_01 | AC | 2 ms
5,536 KB |
testcase_02 | AC | 2 ms
5,812 KB |
testcase_03 | AC | 2 ms
5,544 KB |
testcase_04 | AC | 2 ms
5,596 KB |
testcase_05 | AC | 3 ms
5,536 KB |
testcase_06 | AC | 2 ms
5,596 KB |
testcase_07 | AC | 2 ms
5,656 KB |
testcase_08 | AC | 2,642 ms
414,532 KB |
testcase_09 | AC | 2,927 ms
414,952 KB |
testcase_10 | AC | 3,563 ms
415,168 KB |
testcase_11 | AC | 4,026 ms
415,028 KB |
testcase_12 | AC | 3,524 ms
414,916 KB |
testcase_13 | AC | 4,042 ms
414,924 KB |
testcase_14 | AC | 3,654 ms
414,964 KB |
testcase_15 | AC | 3,520 ms
414,944 KB |
testcase_16 | AC | 3,750 ms
414,952 KB |
testcase_17 | AC | 3,595 ms
414,952 KB |
testcase_18 | AC | 4,067 ms
415,012 KB |
testcase_19 | AC | 3,306 ms
415,008 KB |
testcase_20 | AC | 2,889 ms
415,016 KB |
testcase_21 | AC | 3,724 ms
415,000 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 1 ms
4,384 KB |
testcase_24 | AC | 3 ms
7,612 KB |
ソースコード
#include<iostream> #include<string> #include<iomanip> #include<cmath> #include<vector> #include<algorithm> using namespace std; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") // #define int short #define endl "\n" const long long INF = (long long)1e18; const long long MOD = (long long)1e9 + 7; string yn(bool f){return f?"Yes":"No";} string YN(bool f){return f?"YES":"NO";} const int NUM = 26; int H, W, K; int con[2005][2005][26]; string squares[2000]; inline int check(int y, int x, int sz){ sz--; if(sz < 0) return 0; int y2 = y + sz, x2 = x + sz; if(y2 >= H || x2 >= W) return NUM+1; int level = 0; for(int i = 0; i < NUM; i++){ level += !!(con[y2+1][x2+1][i] - con[y2+1][x][i] - con[y][x2+1][i] + con[y][x][i]); } return level; } signed main(){ cin.tie(0); ios::sync_with_stdio(false); // cout<<fixed<<setprecision(10); long long ans = 0; cin>>H>>W>>K; for(int i = 0; i < H; i++){ cin>>squares[i]; for(int j = 0; j < W; j++){ con[i+1][j+1][squares[i][j] - 'a']++; } } for(int k = 0; k < NUM; k++){ for(int i = 0; i <= H; i++){ for(int j = 0; j <= W; j++){ con[i][j+1][k] += con[i][j][k]; if(i) con[i][j][k] += con[i-1][j][k]; } } } for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ int minimum = (H-i < W-j)?H-i:W-j; int h = minimum + 1, l = 0, m, a; while(l + 1 < h){ m = (l + h)/2; if(check(i,j,m) > K){ h = m; } else { l = m; } } a = h; h = minimum + 1, l = 0; while(l + 1 < h){ m = (l + h)/2; if(!(check(i,j,m) < K)){ h = m; } else { l = m; } } ans += a - l - 1; } } cout<<ans<<endl; return 0; }