結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー Tawara
提出日時 2016-03-14 19:25:44
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,320 bytes
コンパイル時間 882 ms
コンパイル使用メモリ 41,856 KB
実行使用メモリ 11,124 KB
最終ジャッジ日時 2024-10-15 19:42:54
合計ジャッジ時間 2,501 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0