結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-16 22:53:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,913 ms / 6,000 ms |
コード長 | 5,973 bytes |
コンパイル時間 | 1,672 ms |
コンパイル使用メモリ | 172,872 KB |
実行使用メモリ | 414,236 KB |
最終ジャッジ日時 | 2024-09-22 20:20:05 |
合計ジャッジ時間 | 25,874 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
// warm heart, wagging tail,and a smile just for you!//// ▒█████▒▒// ██████████▒// ▒████████████▒// ██████████████████// ████████████████████▒// ▒██████████████████████▒// ▒███████████████████████// ▒████▒▒▒▒▒▒█████████████████▒// ███▒▒▒▒▒▒██████████████████████▒▒▒// ▒██▒▒███████████████████████▒▒▒▒▒██████// ▒█████████████████████████▒▒▒▒▒▒█████████▒// ▒█████████████████████▒▒▒▒▒▒██████████████// ▒████ ████▒▒▒▒▒████ ████▒// ▒█████▒ ████ ▒▒▒▒███████ ████ ██████▒// ▒██▒▒▒▒▒ ██████ █████████ ██████ ██▒▒▒██▒// █████████ ████████ █████████ ████████ ▒▒▒▒█████// ▒█████████ ██████ ████████▒ ██████ █████████// ▒██████████ ████ █████▒▒▒▒▒▒ ████ ██████████// ████████████ ▒▒▒▒▒▒▒████████ ███████████▒// ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒// ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒// ▒▒▒▒▒▒▒▒▒██████████████ ███████▒▒▒▒███████████// █████████████████████████ ███████▒▒▒██████████████▒// █████████████████████████████ ███████▒▒▒██████████████████▒// ██████████████████████████████████████████████████████████████████████// ██████████████████████████████████████████████████████████████████▒// ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒//#include "bits/stdc++.h"using namespace std;#define MOD 1000000007//#define MOD 998244353const double EPS = 1e-9;#define INF (1LL<<60)#define D double#define fs first#define sc second//#define int long long#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)#define REP(i,n) FOR(i,0,(n))#define RREP(i,n) RFOR(i,0,(n))#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)#define range(i,a,b) ((a)<=(i) && (i)<(b))#define debug(x) cout << #x << " = " << (x) << endl;#define SP << " " <<typedef pair<int,int> P;typedef vector<int> vec;typedef vector<vector<int>> mat;int cnt[2001][2001][26] = {};int h,w,x;bool check(int u, int v, int mid, bool up){if(u+mid > h || v+mid > w) return false;vec tmp(26,0);REP(i,26) tmp[i] = cnt[u+mid][v+mid][i]+cnt[u][v][i]-cnt[u+mid][v][i]-cnt[u][v+mid][i];int sum = 0;REP(i,26) if(tmp[i]) sum++;//debug(sum);if(up) return x >= sum;else return x > sum;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin >> h >> w >> x;vector<string> s(h);REP(i,h) cin >> s[i];REP(i,h) REP(j,w) cnt[i+1][j+1][s[i][j]-'a']++;REP(i,h) REP(j,w+1) REP(k,26) cnt[i+1][j][k] += cnt[i][j][k];REP(i,h+1) REP(j,w) REP(k,26) cnt[i][j+1][k] += cnt[i][j][k];long long ans = 0;// REP(i,h) REP(j,w){// int id = min(h-i,w-j)+1;// int ng = 0, ok = id;// while (abs(ng-ok)>1) {// int mid = (ng+ok)/2;// (check(i,j,mid,true)?ok:ng) = mid;// }// int ng2 = 0, ok2 = id;// while (abs(ng2-ok2)>1) {// int mid = (ng2+ok2)/2;// (check(i,j,mid,false)?ok2:ng2) = mid;// }// ans += ok-ok2;// //cout << i SP j SP ok SP ok2 << endl;// }for(int v = -h+1; v < w; v++){int j = max(0,v), l = 1, r = 1;FOR(i,h-min(h,h+v),h){// cout << i SP j << endl;while(check(i,j,l,false)) l++;while(check(i,j,r,true)) r++;ans += r-l;r--; l--;j++;}}cout << ans << endl;return 0;}