結果

問題 No.506 限られたジャパリまん
ユーザー LayCurseLayCurse
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0