#1950756

Solution for 2296: Quest of Merchant by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 47    
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 #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags