fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cassert>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. typedef pair<int,int> PII;
  9. typedef pair<PII,int> TPL;
  10. #define mp make_pair
  11.  
  12. const int mr[]={0,-1,1,0};
  13. const int mc[]={1,0,0,-1};
  14.  
  15. char a[35][35];
  16. bool v[35][35];
  17. int dp[35][35],sum[9][35][35];
  18. int hp[1024],at[1024],w[1025];
  19.  
  20. int main(){
  21.     int n,m,p;
  22.     while(scanf("%d%d%d",&n,&m,&p)==3){
  23.         int sr=0,sc=0,tr=0,tc=0;
  24.         for(int i=1;i<=n;i++){
  25.             scanf("%s",a[i]+1);
  26.             for(int j=1;j<=m;j++){
  27.                 if(a[i][j]=='s') a[sr=i][sc=j]='.';
  28.                 if(a[i][j]=='t') a[tr=i][tc=j]='.';
  29.             }
  30.         }
  31.         for(int i=0;i<p;i++) scanf("%d",hp+i);
  32.         for(int i=0;i<p;i++) scanf("%d",at+i);
  33.         int obj=*max_element(hp,hp+p);
  34.         queue<PII> q;
  35.         memset(dp,63,sizeof(dp));
  36.         dp[tr][tc]=1;
  37.         memset(v,0,sizeof(v));
  38.         for(q.push(mp(tr,tc));q.size();q.pop()){
  39.             int r=q.front().first;
  40.             int c=q.front().second;
  41.             v[r][c]=false;
  42.             for(int o=0;o<4;o++){
  43.                 int dr=r+mr[o];
  44.                 int dc=c+mc[o];
  45.                 if(!dr || !dc || dr>n || dc>m
  46.                 || a[dr][dc]=='x'
  47.                 || a[dr][dc]=='k') continue;
  48.                 int cost=dp[r][c]+(a[dr][dc]=='w')+1;
  49.                 if(cost<dp[dr][dc]){
  50.                     dp[dr][dc]=cost;
  51.                     if(!v[dr][dc]){
  52.                         v[dr][dc]=true;
  53.                         q.push(mp(dr,dc));
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.         memset(v,0,sizeof(v));
  59.         while(1){
  60.             v[sr][sc]=true;
  61.             if(sr==tr && sc==tc) break;
  62.             for(int o=0;o<4;o++){
  63.                 int dr=sr+mr[o];
  64.                 int dc=sc+mc[o];
  65.                 if(!dr || !dc || dr>n || dc>m
  66.                 || a[dr][dc]=='x'
  67.                 || a[dr][dc]=='k') continue;
  68.                 int cost=dp[sr][sc]-(a[sr][sc]=='w')-1;
  69.                 if(cost==dp[dr][dc]){
  70.                     sr=dr,sc=dc;
  71.                     break;
  72.                 }
  73.             }
  74.         }
  75.         memset(sum,0,sizeof(sum));
  76.         for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='k'){
  77.             for(int l=1;l<9;l++){
  78.                 sum[l][i][j]=sum[l-1][i][j];
  79.                 for(int x=0;x<l;x++){
  80.                     int dr,dc;
  81.                     dr=i+x,dc=j+l-x;
  82.                     if(dr>=1 && dc>=1 && dr<=n && dc<=m && v[dr][dc])
  83.                         sum[l][i][j]+=(a[dr][dc]=='w')+1;
  84.                     dr=i+l-x,dc=j-x;
  85.                     if(dr>=1 && dc>=1 && dr<=n && dc<=m && v[dr][dc])
  86.                         sum[l][i][j]+=(a[dr][dc]=='w')+1;
  87.                     dr=i-x,dc=j-l+x;
  88.                     if(dr>=1 && dc>=1 && dr<=n && dc<=m && v[dr][dc])
  89.                         sum[l][i][j]+=(a[dr][dc]=='w')+1;
  90.                     dr=i-l+x,dc=j+x;
  91.                     if(dr>=1 && dc>=1 && dr<=n && dc<=m && v[dr][dc])
  92.                         sum[l][i][j]+=(a[dr][dc]=='w')+1;
  93.                 }
  94.             }
  95.             sum[0][i][j]=0;
  96.             for(int o=0;o<4;o++){
  97.                 int dr=i,dc=j,now=0;
  98.                 while(1){
  99.                     dr+=mr[o];
  100.                     dc+=mc[o];
  101.                     if(!dr || !dc || dr>n || dc>m
  102.                     || a[dr][dc]=='x'
  103.                     || a[dr][dc]=='k') break;
  104.                     if(v[dr][dc]) now+=(a[dr][dc]=='w')+1;
  105.                 }
  106.                 sum[0][i][j]=max(sum[0][i][j],now);
  107.             }
  108.         }
  109.         int R1,S1,T1,U1,V1,W1,L1;
  110.         int R2,S2,T2,U2,V2,W2,L2,X2;
  111.         scanf("%d%d%d%d%d%d%d",&R1,&S1,&T1,&U1,&V1,&W1,&L1);
  112.         scanf("%d%d%d%d%d%d%d%d",&R2,&S2,&T2,&U2,&V2,&W2,&L2,&X2);
  113.         memset(w,63,sizeof(w));
  114.         w[0]=0;
  115.         for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='k'){
  116.             vector<PII> u;
  117.             for(int x=0;x<L1;x++){
  118.                 int use=R1+U1*x;
  119.                 int dmg=T1+W1*x;
  120.                 int spd=S1+V1*x;
  121.                 u.push_back(mp(use,dmg*spd*sum[0][i][j]));
  122.             }
  123.             for(int x=0;x<L2;x++){
  124.                 int use=R2+U2*x;
  125.                 int dmg=T2+W2*x;
  126.                 int spd=S2+V2*x;
  127.                 u.push_back(mp(use,dmg*spd*sum[X2][i][j]));
  128.             }
  129.             for(int c=obj;~c;c--){
  130.                 for(size_t x=0;x<u.size();x++)
  131.                     w[c]=min(w[c],w[max(c-u[x].second,0)]+u[x].first);
  132.             }
  133.         }
  134.         if(w[obj]>1000000000) puts("Happy summer holiday!");
  135.         else printf("%d\n",w[obj]);
  136.     }
  137. }
  138.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Flhy5U
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!