結果
問題 | No.506 限られたジャパリまん |
ユーザー |
![]() |
提出日時 | 2017-04-19 22:46:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,885 bytes |
コンパイル時間 | 841 ms |
コンパイル使用メモリ | 96,120 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-28 04:08:37 |
合計ジャッジ時間 | 1,833 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include<iostream>#include<vector>#include<string>#include<algorithm>#include<map>#include<set>#include<utility>#include<cmath>#include<cstring>#include<queue>#include<stack>#include<cstdio>#include<sstream>#include<iomanip>#include<assert.h>#define loop(i,a,b) for(int i=a;i<b;i++)#define rep(i,a) loop(i,0,a)#define pb push_back#define mt make_tuple#define all(in) in.begin(),in.end()#define shosu(x) fixed<<setprecision(x)using namespace std;//kaewasuretyuuitypedef long long ll;typedef pair<int,int> pii;typedef vector<ll> vi;typedef vector<vi> vvi;typedef vector<pii> vp;typedef vector<vp> vvp;typedef vector<string> vs;typedef vector<double> vd;typedef tuple<int,int,int> tp;typedef vector<tp> vt;typedef vector<vd> vvd;typedef pair<int,pii> pip;typedef vector<pip>vip;const double PI=acos(-1);const double EPS=1e-7;const int inf=1e8;const ll INF=1e16;int dx[]={0,1,0,-1};int dy[]={1,0,-1,0};int main(){int h,w,k,p;cin>>h>>w>>k>>p;assert(1<=h&&h<=32);assert(1<=w&&w<=32);assert(1<=k&&k<=20);assert(0<=p&&p<=k);vs nam(k);vp in(k);rep(i,k)cin>>in[i].first>>in[i].second>>nam[i];rep(i,k)assert(1<=nam[i].size()&&nam[i].size()<=10);rep(i,k)assert(0<=in[i].first&&in[i].first<=h);rep(i,k)assert(0<=in[i].second&&in[i].second<=w);rep(i,k)rep(j,k)if(i!=j){assert(in[i]!=in[j]);assert(nam[i]!=nam[j]);}vi q(k);vi out;ll ma=0,co=0;rep(i,p)q[k-1-i]=1;do{vvi dp(h+2,vi(w+2));dp[1][1]=1;rep(i,h+1)rep(j,w+1){if(i+j==0)continue;bool h=true;rep(r,k)if(!q[r]&&in[r].first==i&&in[r].second==j)h=false;if(h)dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1];}if(ma<dp[h+1][w+1]){ma=dp[h+1][w+1];out=q;co=1;}else if(ma==dp[h+1][w+1])co++;}while(next_permutation(all(q)));if(ma)assert(co==1);cout<<ma%1000000007<<endl;rep(i,out.size())if(out[i])cout<<nam[i]<<endl;}//*/