Submission #767326

#TimeUsernameProblemLanguageResultExecution timeMemory
767326GrindMachineTravelling Merchant (APIO17_merchant)C++17
100 / 100
86 ms4264 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: https://usaco.guide/problems/apio-2017traveling-merchant/solution some submissions to identify the bug in my code (it was in the input taking part) profit = cost/length lets say profit = cost (we ignore length for now) how to solve for this case? for every pair (u,v), create an edge if v is reachable from u this graph says: if we are @u with an empty bag, we buy something @u, then sell it @v, what's the max profit? the weights of the edges denote this profit (we can also choose to buy nothing, weight = 0) find the max cost cycle (inf possible) come back to original problem profit = cost/length we also consider length so when buying something from u and selling it @v, it's optimal to take the shortest path from u to v so for every pair (u,v), we compute: (max_add, shortest_path) profit function is a ratio, annoying to deal with think b.s in such cases how to check if profit >= mid? cost/length >= mid cost >= mid*length cost - mid*length >= 0 edge (max_add, shortest_path) becomes: edge with weight (max_add - mid*shortest_path) find if there is a cycle with sum of weights >= 0 => floyd-warshalls */ const int MOD = 1e9 + 7; const int N = 100 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; const int K = 1e3 + 5; ll buy[N][K], sell[N][K]; ll sp[N][N], best_buy_sell[N][N]; ll weight[N][N], lp[N][N]; // lp = longest path void solve(int test_case) { ll n,m,k; cin >> n >> m >> k; rep1(i,n){ rep1(j,k){ cin >> buy[i][j] >> sell[i][j]; } } memset(sp,0x10,sizeof sp); rep1(i,m){ ll u,v,w; cin >> u >> v >> w; sp[u][v] = w; } rep1(p,n){ rep1(i,n){ rep1(j,n){ amin(sp[i][j], sp[i][p] + sp[p][j]); } } } rep1(i,n){ rep1(j,n){ if(i == j) conts; if(sp[i][j] >= inf2) conts; rep1(p,k){ if(buy[i][p] != -1 and sell[j][p] != -1){ ll val = sell[j][p] - buy[i][p]; amax(best_buy_sell[i][j], val); } } } } auto ok = [&](ll mid){ memset(weight,-0x10,sizeof weight); memset(lp,-0x10,sizeof lp); rep1(i,n){ rep1(j,n){ if(i == j) conts; if(sp[i][j] >= inf2) conts; ll w = best_buy_sell[i][j] - mid*sp[i][j]; if(w > -inf2){ weight[i][j] = lp[i][j] = w; } } } rep1(p,n){ rep1(i,n){ rep1(j,n){ amax(lp[i][j], lp[i][p] + lp[p][j]); amin(lp[i][j], inf2); } } } rep1(i,n){ rep1(j,n){ if(i == j) conts; ll w = lp[i][j] + lp[j][i]; if(w >= 0){ return true; } } } return false; }; ll l = 0, r = inf1; ll ans = -inf2; while(l <= r){ ll mid = (l+r) >> 1; if(ok(mid)){ ans = mid; l = mid+1; } else{ r = mid-1; } } cout << ans << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...