結果

問題 No.655 E869120 and Good Triangles
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-02-24 00:10:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,934 ms / 2,500 ms
コード長 1,826 bytes
コンパイル時間 987 ms
コンパイル使用メモリ 84,840 KB
実行使用メモリ 301,476 KB
最終ジャッジ日時 2024-10-10 02:44:06
合計ジャッジ時間 32,366 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
128,640 KB
testcase_01 AC 37 ms
128,640 KB
testcase_02 AC 34 ms
128,640 KB
testcase_03 AC 35 ms
128,640 KB
testcase_04 AC 35 ms
128,640 KB
testcase_05 AC 35 ms
128,768 KB
testcase_06 AC 35 ms
128,640 KB
testcase_07 AC 36 ms
128,640 KB
testcase_08 AC 36 ms
128,640 KB
testcase_09 AC 35 ms
128,640 KB
testcase_10 AC 1,934 ms
294,784 KB
testcase_11 AC 1,555 ms
300,532 KB
testcase_12 AC 1,591 ms
300,392 KB
testcase_13 AC 1,619 ms
300,888 KB
testcase_14 AC 1,595 ms
300,372 KB
testcase_15 AC 1,699 ms
300,100 KB
testcase_16 AC 1,840 ms
301,476 KB
testcase_17 AC 1,783 ms
300,756 KB
testcase_18 AC 1,764 ms
301,288 KB
testcase_19 AC 1,648 ms
301,392 KB
testcase_20 AC 1,798 ms
300,956 KB
testcase_21 AC 1,743 ms
301,136 KB
testcase_22 AC 1,540 ms
301,288 KB
testcase_23 AC 1,524 ms
299,740 KB
testcase_24 AC 1,051 ms
285,648 KB
testcase_25 AC 1,032 ms
285,648 KB
testcase_26 AC 1,027 ms
285,652 KB
testcase_27 AC 1,181 ms
285,524 KB
testcase_28 AC 998 ms
285,648 KB
testcase_29 AC 1,091 ms
285,780 KB
testcase_30 AC 36 ms
130,512 KB
testcase_31 AC 34 ms
130,516 KB
testcase_32 AC 36 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