結果
問題 | No.506 限られたジャパリまん |
ユーザー |
![]() |
提出日時 | 2017-04-21 22:59:05 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 3,266 bytes |
コンパイル時間 | 1,286 ms |
コンパイル使用メモリ | 159,484 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-28 04:10:46 |
合計ジャッジ時間 | 2,103 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include<bits/stdc++.h>using namespace std;void rd(int &x){int k, m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}void rd(char c[]){int i, sz=0;for(;;){i = getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c[sz++] = i;for(;;){i = getchar_unlocked();if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){break;}c[sz++] = i;}c[sz]='\0';}void wt_L(long long x){char f[20];int m=0, s=0;if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){putchar_unlocked('-');}while(s--){putchar_unlocked(f[s]+'0');}}void wt_L(const char c[]){int i=0;for(i=0;c[i]!='\0';i++){putchar_unlocked(c[i]);}}char name[15][15];int K, P, PX[15], PY[15], X, Y;long long dp[33][33];int main(){int bc, i, j, k, mask, resmask;long long res, tmp;rd(X);rd(Y);rd(K);rd(P);{int Lj4PdHRW;for(Lj4PdHRW=0;Lj4PdHRW<K;Lj4PdHRW++){rd(PX[Lj4PdHRW]);rd(PY[Lj4PdHRW]);rd(name[Lj4PdHRW]);}}res = 0;resmask = 0;for(mask=0;mask<1<<K;mask++){bc = 0;for(i=0;i<K;i++){if(mask&1<<i){bc++;}}if(bc != P){continue;}{int KL2GvlyY;for(KL2GvlyY= 0;KL2GvlyY< (Y) + 1;KL2GvlyY++){{int Q5VJL1cS;for(Q5VJL1cS= 0;Q5VJL1cS< (X) + 1;Q5VJL1cS++){dp[Q5VJL1cS][KL2GvlyY] = 0;}}}}for(i=0;i<K;i++){if(!(mask&1<<i)){dp[PX[i]][PY[i]] = -1;}}dp[0][0] = 1;for(i=0;i<X+1;i++){for(j=0;j<Y+1;j++){if(dp[i][j]==-1){continue;}if(i && dp[i-1][j]>0){dp[i][j] += dp[i-1][j];}if(j && dp[i][j-1]>0){dp[i][j] += dp[i][j-1];}}}if(res < dp[X][Y]){res = dp[X][Y];resmask = mask;}}wt_L(res%(1000000000+7));putchar_unlocked('\n');for(i=0;i<K;i++){if(resmask & 1<<i){wt_L(name[i]);putchar_unlocked('\n');}}return 0;}// cLay varsion 20170421-1 [beta]// --- original code ---// int X, Y, K, P;// int PX[15], PY[15];// char name[15][15];//// ll dp[33][33];// {// int i, j, k;// int mask, bc, resmask;// ll res, tmp;//// reader(X,Y,K,P,(PX,PY,name)(K));//// res = 0;// resmask = 0;// rep(mask,1<<K){// bc = 0;// rep(i,K) if(mask&1<<i) bc++;// if(bc != P) continue;//// dp[0..X][0...Y] = 0;// rep(i,K) if(!(mask&1<<i)) dp[PX[i]][PY[i]] = -1;//// dp[0][0] = 1;// rep(i,X+1) rep(j,Y+1){// if(dp[i][j]==-1) continue;// if(i && dp[i-1][j]>0) dp[i][j] += dp[i-1][j];// if(j && dp[i][j-1]>0) dp[i][j] += dp[i][j-1];// }//// if(res < dp[X][Y]){// res = dp[X][Y];// resmask = mask;// }// }//// wt(res%(1d9+7));// rep(i,K) if(resmask & 1<<i) wt(name[i]);// }