結果

問題 No.655 E869120 and Good Triangles
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-02-24 00:10:40
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,041 ms / 2,500 ms
コード長 1,826 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 86,976 KB
実行使用メモリ 294,912 KB
最終ジャッジ日時 2024-04-18 09:28:37
合計ジャッジ時間 36,986 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 95 ms
128,640 KB
testcase_01 AC 95 ms
128,640 KB
testcase_02 AC 95 ms
128,640 KB
testcase_03 AC 94 ms
128,768 KB
testcase_04 AC 95 ms
128,768 KB
testcase_05 AC 95 ms
128,768 KB
testcase_06 AC 95 ms
128,640 KB
testcase_07 AC 96 ms
128,640 KB
testcase_08 AC 95 ms
128,768 KB
testcase_09 AC 96 ms
128,768 KB
testcase_10 AC 1,871 ms
294,912 KB
testcase_11 AC 1,729 ms
294,088 KB
testcase_12 AC 1,798 ms
294,400 KB
testcase_13 AC 1,811 ms
294,912 KB
testcase_14 AC 1,797 ms
294,656 KB
testcase_15 AC 1,883 ms
294,644 KB
testcase_16 AC 2,041 ms
294,784 KB
testcase_17 AC 1,986 ms
294,616 KB
testcase_18 AC 1,944 ms
294,784 KB
testcase_19 AC 1,845 ms
294,912 KB
testcase_20 AC 1,979 ms
294,500 KB
testcase_21 AC 1,942 ms
294,656 KB
testcase_22 AC 1,794 ms
294,784 KB
testcase_23 AC 1,835 ms
294,912 KB
testcase_24 AC 1,203 ms
283,776 KB
testcase_25 AC 1,187 ms
283,520 KB
testcase_26 AC 1,177 ms
283,776 KB
testcase_27 AC 1,344 ms
283,648 KB
testcase_28 AC 1,119 ms
283,520 KB
testcase_29 AC 1,250 ms
283,648 KB
testcase_30 AC 99 ms
128,640 KB
testcase_31 AC 99 ms
128,768 KB
testcase_32 AC 99 ms
128,640 KB
権限があれば一括ダウンロードができます

ソースコード

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