結果
問題 |
No.866 レベルKの正方形
|
ユーザー |
|
提出日時 | 2025-08-07 19:02:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,477 ms / 6,000 ms |
コード長 | 1,169 bytes |
コンパイル時間 | 3,311 ms |
コンパイル使用メモリ | 284,128 KB |
実行使用メモリ | 211,780 KB |
最終ジャッジ日時 | 2025-08-07 19:02:33 |
合計ジャッジ時間 | 29,493 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define i64 long long const int MAX=2005; static uint16_t d[26][MAX][MAX]; static char g[MAX][MAX]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int h,w,k; cin>>h>>w>>k; for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)cin>>g[i][j]; const uint16_t INF=6000; for(int x=0;x<26;x++){ for(int i=0;i<=h+1;i++)for(int j=0;j<=w+1;j++)d[x][i][j]=INF; for(int i=h;i>=1;i--)for(int j=w;j>=1;j--){ if(g[i][j]=='a'+x)d[x][i][j]=0; else{ uint16_t u=d[x][i+1][j],v=d[x][i][j+1],t0=d[x][i+1][j+1],m=u<v?u:v; if(t0<m)m=t0; d[x][i][j]=m+1; } } } i64 ans=0; uint16_t b[26]; for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){ for(int x=0;x<26;x++)b[x]=d[x][i][j]+1; nth_element(b,b+k-1,b+26); uint16_t Lk=b[k-1],Lk1=INF; if(k<26){ nth_element(b,b+k,b+26); Lk1=b[k]; } int r=min(h-i+1,w-j+1); int m1=min((int)Lk-1,r),m2=min((int)Lk1-1,r); if(m2>m1)ans+=m2-m1; } cout<<ans<<"\n"; return 0; }