結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 4 ms
7,756 KB
in02.txt AC 4 ms
7,752 KB
in03.txt AC 4 ms
8,912 KB
in04.txt AC 3 ms
7,756 KB
in05.txt AC 4 ms
8,912 KB
in06.txt AC 3 ms
7,752 KB
in07.txt AC 3 ms
7,752 KB
in08.txt AC 3 ms
7,752 KB
in09.txt AC 5 ms
7,756 KB
in10.txt AC 4 ms
7,756 KB
in11.txt AC 292 ms
437,748 KB
in12.txt AC 273 ms
437,748 KB
in13.txt AC 281 ms
437,748 KB
in14.txt AC 277 ms
437,744 KB
in15.txt AC 277 ms
437,748 KB
in16.txt AC 288 ms
437,744 KB
in17.txt AC 304 ms
437,744 KB
in18.txt AC 303 ms
437,748 KB
in19.txt AC 297 ms
437,744 KB
in20.txt AC 285 ms
437,744 KB
in21.txt AC 302 ms
437,748 KB
in22.txt AC 295 ms
437,748 KB
in23.txt AC 273 ms
437,744 KB
in24.txt AC 269 ms
437,744 KB
in25.txt AC 225 ms
437,744 KB
in26.txt AC 223 ms
437,748 KB
in27.txt AC 224 ms
437,748 KB
in28.txt AC 256 ms
437,744 KB
in29.txt AC 224 ms
437,744 KB
in30.txt AC 238 ms
437,748 KB
sample_01.txt AC 5 ms
7,744 KB
sample_02.txt AC 4 ms
7,748 KB
sample_03.txt AC 5 ms
7,752 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