Submission #260101

#TimeUsernameProblemLanguageResultExecution timeMemory
260101user202729Travelling Merchant (APIO17_merchant)C++17
100 / 100
112 ms3576 KiB
// 6 #ifndef LOCAL #define NDEBUG 1 #endif #include<bits/stdc++.h> /* struct Edge{int node, length;}; std::vector<std::vector<Edge>> add; */ int main(){ std::ios::sync_with_stdio(0);std::cin.tie(0); int number, numEdge, numItem; std::cin>>number>>numEdge>>numItem; struct T{int buy, sell;}; std::vector<std::vector<T>> cost(number, std::vector<T>(numItem)); for(auto& it: cost)for(auto& [buy, sell]: it) std::cin>>buy>>sell; std::vector<std::vector<int>> time(number, std::vector<int>(number, INT_MAX/2)); for(int _=0; _<numEdge; ++_){ int first, sec, length; std::cin>>first>>sec>>length; --first;--sec; time[first][sec]=std::min(time[first][sec], length); } for(int k=0; k<number; ++k) for(int i=0; i<number; ++i) for(int j=0; j<number; ++j) time[i][j]=std::min(time[i][j], time[i][k]+time[k][j]); for(auto& it: time)for(auto& it: it){ assert(it>=0); assert(it<=INT_MAX/2); } std::vector<std::vector<int>> maxProfit(number, std::vector<int>(number)); for(int i=0; i<number; ++i) for(int j=0; j<number; ++j){ int cur=0; // 0 is always achievable by doing nothing for(int item=0; item<numItem; ++item) if(cost[j][item].sell>=0 and cost[i][item].buy>=0) cur=std::max(cur, cost[j][item].sell-cost[i][item].buy); maxProfit[i][j]=cur; } struct V{ // A-B*epsilon (B>=0) int64_t value; // least bit=1 -> B=0 bool operator<(V other) const{return value<other.value;} bool operator==(V other) const{return value==other.value;} V operator+(V other) const{return {value+other.value-((value|other.value)&1)};} }; assert(V{1}+V{1}==V{1}); assert(V{1}+V{0}==V{0}); assert(V{0}+V{1}==V{0}); assert(V{0}+V{0}==V{0}); std::vector<std::vector<V>> tmp(number, std::vector<V>(number)); auto const check=[&](int64_t efficient){ for(int i=0; i<number; ++i) for(int j=0; j<number; ++j){ int profit=maxProfit[i][j]; if(i==j) assert(profit==0); int time_=time[i][j]; tmp[i][j]=V{ time_==INT_MAX/2 ? INT64_MAX/2: ((time_*efficient-profit)*2+(profit==0)) }; } for(int k=0; k<number; ++k) for(int i=0; i<number; ++i) for(int j=0; j<number; ++j) tmp[i][j]=std::min(tmp[i][j], tmp[i][k]+tmp[k][j]); for(int i=0; i<number; ++i) if(tmp[i][i]<V{1}) return true; return false; }; int i=0; for(int step=1<<30; step; step>>=1){ if(check(i+step)) i+=step; } std::cout<<i<<'\n'; }

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:31:31: warning: unused variable 'it' [-Wunused-variable]
  for(auto& it: time)for(auto& it: it){
                               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...