## #1950756

Solution for 2296: Quest of Merchant by btk

Source Code Status Test Cases
Policy: public     Reviewed: 74
00.02 sec    3344 KB    78 lines     1913 bytes    2016-08-04 17:09
```#include<bits/stdc++.h>

using namespace  std;

struct I{I(){ios::sync_with_stdio(false);cin.tie(0);}}init;

typedef long long LL;
typedef vector<LL> V;

const LL INF=1145141919;
V TSP(V &x,V &y){
int n=x.size();
V res(1<<n,INF);
vector<V> tsp(n,V(1<<n,INF));
V ord((1<<n)-1);
iota(ord.begin(),ord.end(),1);
sort(ord.begin(),ord.end(),[&](int l,int r){return __builtin_popcount(l)<__builtin_popcount(r);});
for(int i=0;i<n;i++)tsp[i][1<<i]=abs(x[i])+abs(y[i]);
for(auto &bit:ord){
for(int i=0;i<n;i++){
res[bit]=min(res[bit],tsp[i][bit]+abs(x[i])+abs(y[i]));
for(int j=0;j<n;j++){
int c=1<<j;
tsp[j][bit|c]=min(tsp[j][bit|c],tsp[i][bit]+abs(x[i]-x[j])+abs(y[i]-y[j]));
}
}
}
return res;
}
LL knapsack(V cost,V value,int limit){
int n=cost.size();
LL res=0;
V dp(limit+1,0);
for(int i=0;i<n;i++)
for(int j=cost[i];j<=limit;j++)
res=max(dp[j]=max(dp[j],dp[j-cost[i]]+value[i]),res);
return res;
}

int main(){
int N,M,W,T;
cin>>N>>M>>W>>T;
V w(M),v(M);
map<string,int> StoI;
for(int i=0;i<M;i++){
string s;
cin>>s>>w[i]>>v[i];
StoI[s]=i;
}
V x(N),y(N);
vector<V> valdp(1<<N,V(M,0));
V val(1<<N,0);
for(int i=0;i<N;i++){
int L;cin>>L>>x[i]>>y[i];
while(L--){
string s;LL vv;cin>>s>>vv;
int id=StoI[s];
vv=max(0ll,v[id]-vv);
valdp[1<<i][id]=vv;
}
}
auto t=TSP(x,y);
for(int bit=1;bit<(1<<N);bit++){
int rest=bit;
while(rest){
int now=rest&-rest;
for(int i=0;i<M;i++)
valdp[bit][i]=max(valdp[bit][i],valdp[now][i]);
rest-=now;
}
val[bit]=knapsack(w,valdp[bit],W);
}
cout<<knapsack(t,val,T)<<endl;
return 0;
}

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 72/72 C++11 CPU: 00.02 sec Memory: 3344 KB Length: 1913 B 2016-08-04 17:09 2016-08-04 17:09
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.00 sec 3204 KB Case #2: : Accepted 00.00 sec 3124 KB Case #3: : Accepted 00.01 sec 3328 KB Case #4: : Accepted 00.02 sec 3212 KB Case #5: : Accepted 00.00 sec 3192 KB Case #6: : Accepted 00.01 sec 3296 KB Case #7: : Accepted 00.02 sec 3344 KB Case #8: : Accepted 00.00 sec 3280 KB Case #9: : Accepted 00.00 sec 3140 KB Case #10: : Accepted 00.00 sec 3252 KB Case #11: : Accepted 00.00 sec 3136 KB Case #12: : Accepted 00.00 sec 3036 KB Case #13: : Accepted 00.01 sec 3208 KB Case #14: : Accepted 00.01 sec 3232 KB Case #15: : Accepted 00.01 sec 3208 KB Case #16: : Accepted 00.01 sec 3252 KB Case #17: : Accepted 00.01 sec 3268 KB Case #18: : Accepted 00.01 sec 3196 KB Case #19: : Accepted 00.01 sec 3276 KB Case #20: : Accepted 00.01 sec 3268 KB Case #21: : Accepted 00.01 sec 3232 KB Case #22: : Accepted 00.01 sec 3328 KB Case #23: : Accepted 00.01 sec 3272 KB Case #24: : Accepted 00.01 sec 3196 KB Case #25: : Accepted 00.01 sec 3132 KB Case #26: : Accepted 00.01 sec 3116 KB Case #27: : Accepted 00.01 sec 3296 KB Case #28: : Accepted 00.01 sec 3308 KB Case #29: : Accepted 00.01 sec 3308 KB Case #30: : Accepted 00.01 sec 3328 KB Case #31: : Accepted 00.01 sec 3120 KB Case #32: : Accepted 00.01 sec 3208 KB Case #33: : Accepted 00.01 sec 3272 KB Case #34: : Accepted 00.01 sec 3216 KB Case #35: : Accepted 00.01 sec 3244 KB Case #36: : Accepted 00.01 sec 3324 KB Case #37: : Accepted 00.01 sec 3256 KB Case #38: : Accepted 00.01 sec 3296 KB Case #39: : Accepted 00.00 sec 3116 KB Case #40: : Accepted 00.00 sec 3148 KB Case #41: : Accepted 00.00 sec 3196 KB Case #42: : Accepted 00.00 sec 3148 KB Case #43: : Accepted 00.00 sec 3060 KB Case #44: : Accepted 00.00 sec 3188 KB Case #45: : Accepted 00.00 sec 3156 KB Case #46: : Accepted 00.00 sec 3256 KB Case #47: : Accepted 00.00 sec 3120 KB Case #48: : Accepted 00.00 sec 3048 KB Case #49: : Accepted 00.00 sec 3152 KB Case #50: : Accepted 00.00 sec 3192 KB Case #51: : Accepted 00.00 sec 3176 KB Case #52: : Accepted 00.00 sec 3172 KB Case #53: : Accepted 00.00 sec 3200 KB Case #54: : Accepted 00.00 sec 3172 KB Case #55: : Accepted 00.00 sec 3176 KB Case #56: : Accepted 00.00 sec 3172 KB Case #57: : Accepted 00.00 sec 3136 KB Case #58: : Accepted 00.00 sec 3256 KB Case #59: : Accepted 00.00 sec 3172 KB Case #60: : Accepted 00.00 sec 3268 KB Case #61: : Accepted 00.00 sec 3156 KB Case #62: : Accepted 00.00 sec 3192 KB Case #63: : Accepted 00.01 sec 3132 KB Case #64: : Accepted 00.01 sec 3296 KB Case #65: : Accepted 00.01 sec 3132 KB Case #66: : Accepted 00.01 sec 3204 KB Case #67: : Accepted 00.01 sec 3296 KB Case #68: : Accepted 00.01 sec 3196 KB Case #69: : Accepted 00.01 sec 3116 KB Case #70: : Accepted 00.01 sec 3216 KB Case #71: : Accepted 00.01 sec 3264 KB Case #72: : Accepted 00.01 sec 3292 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )