結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー TawaraTawara
提出日時 2016-03-14 19:25:44
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,320 bytes
コンパイル時間 674 ms
コンパイル使用メモリ 41,772 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-04-23 18:55:27
合計ジャッジ時間 1,733 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 8 ms
11,008 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 7 ms
10,880 KB
testcase_07 AC 8 ms
11,008 KB
testcase_08 AC 8 ms
11,008 KB
testcase_09 AC 8 ms
11,008 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 8 ms
10,900 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 8 ms
11,008 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 8 ms
11,008 KB
testcase_19 AC 8 ms
11,136 KB
testcase_20 AC 8 ms
11,008 KB
testcase_21 AC 7 ms
11,008 KB
testcase_22 AC 8 ms
11,092 KB
testcase_23 AC 8 ms
11,008 KB
testcase_24 AC 8 ms
11,008 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:30:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |         scanf("%d %d %d",&Gx,&Gy,&K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
main.cpp:35:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |                 scanf("%d %d %d",&x,&y,&N); p = P(x,y); shift = i*4;
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

struct P {
	int x,y;
	P() {}
	P(int x, int y) : x(x), y(y){}
	P operator + (P p){return P(x + p.x, y + p.y);}
	P operator * (int d){return P(x*d, y*d);}
	bool operator == (P p){return (x == p.x && y == p.y);}
	bool operator != (P p){return (x != p.x || y != p.y);}
};

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)
#define MOD 1000000007

LL C[76][76];

int main(){
	int Gx,Gy,K,x,y,N,shift,mul,total,dup_n;
	LL tmp,ans = 0;
	P p,mp,g,np = P(MOD,MOD);
	vector <P> dp(1<<20);
	scanf("%d %d %d",&Gx,&Gy,&K);
	rep(i,1<<(K*4)) dp[i] = np;
	dp[0] = P(0,0); g = P(Gx,Gy); C[0][0] = 1;
	rep(i,K*15) rep(j,i+2) C[i+1][j] = (C[i][j]+(j>0 ? C[i][j-1]:0))%MOD;
	rep(i,K){
		scanf("%d %d %d",&x,&y,&N); p = P(x,y); shift = i*4;
		for (int j = 0; N > 0; j++){
			mul = min(1<<j,N); mp = p * mul; N-=mul;
			for (int k = (1<<(j+shift))-1; k >= 0; k--){
				if (dp[k] == np) continue;
				dp[k+(mul<<shift)] = dp[k] + mp;
			}
		}
	}
	rep(k,1<<(K*4)){
		if (dp[k] != g) continue;
		total = 0; tmp = 1;
		rep(i,K) total+=(k>>(i*4))%16;
		rep(i,K){
			dup_n = (k>>(i*4))%16;
			tmp = tmp * C[total][dup_n] % MOD;
			total-=dup_n;
		}
		ans = (ans + tmp) % MOD;
	}
	printf("%lld\n",ans);
	return 0;
}
0