結果

問題 No.655 E869120 and Good Triangles
ユーザー WA_TLE
提出日時 2018-02-01 19:46:28
言語 C++17(1z)
(gcc 9.2.0)
結果
AC  
実行時間 401 ms
コード長 3,387 Byte
コンパイル時間 1,132 ms
使用メモリ 279,284 KB
最終ジャッジ日時 2019-12-28 01:15:12

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 3 ms
1,676 KB
in02.txt AC 3 ms
1,676 KB
in03.txt AC 3 ms
1,676 KB
in04.txt AC 3 ms
1,676 KB
in05.txt AC 3 ms
1,672 KB
in06.txt AC 3 ms
1,676 KB
in07.txt AC 3 ms
1,672 KB
in08.txt AC 3 ms
1,672 KB
in09.txt AC 2 ms
1,672 KB
in10.txt AC 3 ms
1,672 KB
in11.txt AC 386 ms
279,284 KB
in12.txt AC 361 ms
279,284 KB
in13.txt AC 383 ms
279,284 KB
in14.txt AC 379 ms
279,280 KB
in15.txt AC 378 ms
279,280 KB
in16.txt AC 383 ms
279,280 KB
in17.txt AC 400 ms
279,280 KB
in18.txt AC 400 ms
279,284 KB
in19.txt AC 401 ms
279,280 KB
in20.txt AC 395 ms
279,280 KB
in21.txt AC 399 ms
279,284 KB
in22.txt AC 391 ms
279,280 KB
in23.txt AC 372 ms
279,280 KB
in24.txt AC 375 ms
279,284 KB
in25.txt AC 329 ms
279,280 KB
in26.txt AC 327 ms
279,280 KB
in27.txt AC 328 ms
279,284 KB
in28.txt AC 373 ms
279,280 KB
in29.txt AC 330 ms
279,284 KB
in30.txt AC 342 ms
279,280 KB
sample_01.txt AC 2 ms
1,640 KB
sample_02.txt AC 3 ms
1,656 KB
sample_03.txt AC 2 ms
1,676 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;
const llint big=(llint)44e15;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int main(void){
	//ういーんビートビートひるどww
	llint n,K,p,i,j;cin>>n>>K>>p;
	static int a[4002][4002];
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){a[i][j]=mod;}
	}
	for(i=0;i<K;i++){int x,y;cin>>x>>y;a[x][y]=0;}
	for(i=1;i<=n;i++){
		for(j=1;j<i;j++){mineq(a[i][j+1],a[i][j]+1);}
		for(j=i;j>1;j--){mineq(a[i][j-1],a[i][j]+1);}
	}
	for(i=1;i<n;i++){
		for(j=1;j<=i;j++){mineq(a[i+1][j+1],a[i][j]+1);}
		for(j=1;j<=i;j++){mineq(a[i+1][j],a[i][j]+1);}
	}
	for(i=n;i>1;i--){
		for(j=1;j<i;j++){mineq(a[i-1][j],a[i][j]+1);}
		for(j=2;j<=i;j++){mineq(a[i-1][j-1],a[i][j]+1);}
	}
	//aの値が求まった
	static llint wata[4002][4002]={0};//縦累積和
	static llint wana[4002][4002]={0};//ななめ累積和
	static llint wayo[4002][4002]={0};//ななめ累積和
	for(i=1;i<=n;i++){for(j=1;j<=i;j++){
		wata[i][j]=a[i][j]+wata[i-1][j];
		wana[i][j]=a[i][j]+wana[i-1][j-1];
		wayo[i][j]=a[i][j]+wayo[i][j-1];
	}}
	llint ans=0;
	array<llint,4002> gen={0};//現在の三角の数字
	array<int,4002> made={0};//どこまで
	for(i=1;i<=n;i++){
		array<llint,4002>ngen;
		array<int,4002>nmade;
		for(j=1;j<=i;j++){
			int dco=max(made[j-1],made[j]);
			llint now=0;
			if(dco==made[j-1]){now=gen[j-1]-wata[dco][j-1]+wata[i-1][j-1]-a[i-1][j-1];}
			else{now=gen[j]-wana[dco][dco-i+j+1]+wana[i-1][j]-a[i-1][j];}
			//cerr<<wata[i][j]<<" ";
			while(dco<=n&&now<p){
				dco++;
				now+=wayo[dco][dco-i+j]-wayo[dco][j-1];
			}
			
			ans+=1+n-dco;
			ngen[j]=now;
			nmade[j]=dco;
			
		}
		//cerr<<endl;
		swap(gen,ngen);
		swap(made,nmade);
	}
	cout<<ans<<endl;
}
0