結果

問題 No.655 E869120 and Good Triangles
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2018-02-24 00:10:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,971 ms / 2,500 ms
コード長 1,826 bytes
コンパイル時間 915 ms
コンパイル使用メモリ 82,968 KB
最終ジャッジ日時 2025-01-05 08:46:23
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

const int N=4001;
int x[N],y[N];

bool blk[N][N];
lint a[N][N];
lint b[N][N];
lint c[N][N];
int n,k;
lint p;
void disp(string s,lint a[N][N]){
  cerr<<s<<":"<<endl;
  rep(x,n){
    rep(y,x+1){
      cerr<<" "<<a[x][y];
    }
    cerr<<endl;
  }
}

lint f(int x,int y,int h){
  lint tmp=c[x][y];
  if(x+h<n){
    tmp-=c[x+h][y+h];
    tmp-=b[x+h][y+h-1];
    if(y>0)
      tmp+=b[x+h][y-1];
  }
  if(0){
    cerr<<"f("<<x<<","<<y<<","<<h<<")="<<tmp<<endl;
  }
  return tmp;
}

int main(){
  cin>>n>>k>>p;
  rep(i,k){
    cin>>x[i]>>y[i];
    x[i]--,y[i]--;
    blk[x[i]][y[i]]=1;
  }
  memset(a,-1,sizeof(a));
  queue<pii>que;
  rep(i,k){
    que.push(pii(x[i],y[i]));
    a[x[i]][y[i]]=0;
  }
  int dx[6]={1,1,0,-1,-1,0};
  int dy[6]={0,1,1,0,-1,-1};
  while(!que.empty()){
    pii t=que.front();que.pop();
    int x=t.first,y=t.second;
    int d=a[x][y];
    rep(dir,6){
      int nx=x+dx[dir],ny=y+dy[dir];
      if(nx<0||nx>=n||ny<0||ny>nx)continue;
      if(a[nx][ny]>=0)continue;
      a[nx][ny]=d+1;
      que.push(pii(nx,ny));
    }
  }
  rep(j,n){
    b[n-1][j]=a[n-1][j];
    c[n-1][j]=a[n-1][j];
  }
  for(int i=n-2;i>=0;--i){
    rep(j,i+1){
      b[i][j]=b[i+1][j]+a[i][j];
      c[i][j]=c[i+1][j+1]+b[i][j];
    }
  }
  if(0){
    disp("a",a);
    disp("b",b);
    disp("c",c);
  }
  rep(i,n){
    rep(j,i){
      b[i][j+1]+=b[i][j];
    }
  }
  lint ans=0;
  rep(i,n){
    int lim=n-i;
    rep(j,i+1){
      int hi=lim+1,lo=-1;
      while(hi-lo>1){
	int mid=(hi+lo)/2;
	if(f(i,j,mid)>=p){
	  hi=mid;
	}else{
	  lo=mid;
	}
      }
      ans+=lim+1-hi;
    }
  }
  cout<<ans<<endl;
}
0