長方形のケーキが $R$ 行 $C$ 列のマスに分割されている.
縦も横も $3$ マス以上の長方形の領域を $1$ つ選び,その周ではなく内部の $1$ マスを取り除いたような穴あきケーキを作りたい.
各マス $(i,j)$ のカロリー量 $S_{i,j}$ が与えられる.
総カロリー量が $K$ となるような穴あきケーキの作り方のパターン数を求める問題.
前計算に $O(RCs)$ 時間($s = \max(S_{ij})$)を使って,二次元累積和を用いて,各長方形の領域に $1$ から $9$ のカロリーのマスが何個あるかを $O(1)$ で求められるようにしておく.
穴ケーキの長方形の左端と右端を全探索し,上端と下端は尺取法にて探索する.
尺取法においては,上端を決めると,穴を開ける前の長方形の領域のカロリーの合計が $K+1$ から $K+9$ までとなるような下端を探せば良い.
下端を $1$ マス下に移動させると,最低でもカロリーが $3$ 増えるので,そのような下端の数は最大でも $3$ 個しかない.
後は,余分なカロリー量と同じカロリーのマスが何個あるかを求め,それを足していけば良い.
カロリーの総量を求めるには,考えている範囲において,各行の総カロリーを求めておいたり,もしくはこれも二次元累積和を用いても良い.
時間計算量は $O(RCs+RC^2)$ 程度.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
int X, Y, K;
int S[360][360];
int sum[360];
int cnt[10][360][360];
char buf[360];
inline int get_sum(int x1, int x2, int y1, int y2, int mp[][360]){
return mp[x2+1][y2+1] - mp[x1][y2+1] - mp[x2+1][y1] + mp[x1][y1];
}
int main(){
int i, j, k, cur, tar;
int x1, x2;
ll res = 0;
reader(&X,&Y,&K);
rep(i,X){
reader(buf);
rep(j,Y) S[i][j] = buf[j]-'0';
}
REP(k,1,10) rep(i,X) rep(j,Y){
cnt[k][i+1][j+1] = cnt[k][i+1][j] + cnt[k][i][j+1] - cnt[k][i][j];
if(S[i][j]==k) cnt[k][i+1][j+1]++;
}
rep(x1,X-2){
rep(i,Y) sum[i] = S[x1][i]+S[x1+1][i];
REP(x2,x1+2,X){
rep(i,Y) sum[i] += S[x2][i];
j = 0; cur = sum[0];
rep(i,Y){
while(j < Y && (j<i+2 || cur<=K)) cur += sum[++j];
if(j >= Y) break;
tar = cur - K - sum[j];
REP(k,j,Y){
tar += sum[k];
if(tar>=10) break;
res += get_sum(x1+1,x2-1,i+1,k-1,cnt[tar]);
}
cur -= sum[i];
}
}
}
writerLn(res);
return 0;
}
Current time: 2024年04月27日13時46分04秒
Last modified: 2015年12月09日17時21分36秒 (by laycrs)
Tags: Competitive_Programming AtCoder code-thanks-festival-2015-open
トップページに戻る
Logged in as: unknown user (not login)