結果

問題 No.612 Move on grid
ユーザー kotatsugamekotatsugame
提出日時 2020-03-11 06:07:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,188 bytes
コンパイル時間 756 ms
コンパイル使用メモリ 66,688 KB
実行使用メモリ 84,224 KB
最終ジャッジ日時 2024-11-15 23:57:51
合計ジャッジ時間 53,694 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,496 KB
testcase_01 AC 2 ms
12,288 KB
testcase_02 AC 2 ms
10,496 KB
testcase_03 AC 429 ms
12,416 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 WA -
testcase_12 TLE -
testcase_13 AC 2,010 ms
10,624 KB
testcase_14 TLE -
testcase_15 WA -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
using namespace std;
int T;
int a,b,c,d,e;
long mod=1e9+7;
long comb[501][501],combsum[501][501];
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
main()
{
	cin>>T>>a>>b>>c>>d>>e;
	comb[0][0]=1;
	combsum[0][0]=1;
	for(int i=1;i<=T;i++)
	{
		comb[i][0]=comb[i][i]=1;
		for(int j=1;j<i;j++)comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%mod;
		combsum[i][0]=1;
		for(int j=1;j<=i;j++)combsum[i][j]=(comb[i][j]+combsum[i][j-1])%mod;
	}
	long ans=0;
	for(int i=0;i<=T;i++)for(int ii=0;ii<=T-i;ii++)
	{
		int x=i-ii;
		int Tr=T-i-ii;
		long XW=comb[T][i]*comb[T-i][ii]%mod;
		for(int j=0;j<=Tr;j++)for(int jj=0;jj<=Tr-j;jj++)
		{
			int y=j-jj;
			long XYW=XW*comb[Tr][j]%mod*comb[Tr-j][jj]%mod;
			int Z=Tr-j-jj;
			int D=d-a*x-b*y+c*Z;
			int E=e-a*x-b*y+c*Z;
			int L=0,R=Z;
			if(c==0);
			else if(c>0)
			{
				L=max(L,D/(2*c));
				if(2*c*L<D)L++;
				R=min(R,E/(2*c));
				if(2*c*R>E)R--;
			}
			else
			{
				L=max(L,E/(-2*c));
				if(2*c*L>E)L++;
				R=min(R,D/(-2*c));
				if(2*c*R<D)R--;
			}
			if(L<=R&&D<=2*c*L&&2*c*R<=E)
			{
				long t=(combsum[Z][R]+mod-(L==0?0:combsum[Z][L-1]))%mod;
				(ans+=t*XYW)%=mod;
			}
		}
	}
	cout<<ans<<endl;
}
0