Submission #309796

#TimeUsernameProblemLanguageResultExecution timeMemory
309796vipghn2003Travelling Merchant (APIO17_merchant)C++14
0 / 100
259 ms2296 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair using namespace std; const int N=105; const int K=1005; int n,m,k,d[N][N],buy[N][K],sell[N][K],opt[N][N],w[N][N]; bool check(int lim) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { w[i][j]=-1e18; for(int u=1;u<=n;u++) { if(d[i][u]==-1||d[u][j]==-1) continue; int dist=d[i][u]+d[u][j]; int gain=opt[u][j]; w[i][j]=max(w[i][j],gain-dist*lim); } } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { w[i][j]=max(w[i][j],w[i][k]+w[k][j]); if(w[i][i]>=0) return true; } } } return false; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); memset(d,-1,sizeof d); cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) cin>>buy[i][j]>>sell[i][j]; } while(m--) { int u,v,w; cin>>u>>v>>w; d[u][v]=w; } for(int u=1;u<=n;u++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(d[i][u]==-1||d[u][j]==-1) continue; int val=d[i][u]+d[u][j]; if(d[i][j]==-1||d[i][j]>val) d[i][j]=val; } } } for(int u=1;u<=n;u++) { for(int v=1;v<=n;v++) { opt[u][v]=-1e18; for(int item=1;item<=k;item++) { if(buy[u][item]==-1||sell[v][item]==-1) continue; opt[u][v]=max(opt[u][v],sell[v][item]-buy[u][item]); } } } long long l=1,r=1e18,res=0; while(l<=r) { long long mid=(l+r)/2; if(check(mid)) { res=mid; l=mid+1; } else r=mid-1; } cout<<res; } /* 50 144 5 669304181 -1 479970956 -1 167649828 -1 470258299 -1 885426197 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 952670542 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 485876430 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 893900443 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 575906768 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 941456320 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 32 39 1 49 38 1 21 12 1 35 2 1 32 11 1 46 20 1 4 11 1 26 20 1 18 6 1 48 45 1 20 47 1 18 22 1 47 3 1 43 47 1 13 11 1 13 39 1 27 9 1 34 50 1 11 18 1 4 25 1 41 20 1 26 37 1 28 7 1 7 22 1 1 46 1 3 1 1 46 18 1 47 1 1 41 8 1 11 29 1 47 36 1 43 48 1 33 37 1 45 49 1 42 30 1 30 38 1 47 15 1 3 27 1 32 29 1 17 2 1 50 49 1 4 21 1 48 39 1 28 38 1 34 18 1 31 21 1 50 45 1 16 12 1 1 50 1 44 17 1 43 40 1 32 42 1 41 24 1 8 37 1 20 34 1 23 46 1 42 34 1 7 17 1 21 34 1 30 47 1 27 22 1 6 23 1 33 14 1 31 37 1 7 2 1 22 28 1 48 32 1 30 5 1 22 35 1 39 19 1 6 36 1 5 3 1 30 23 1 45 12 1 23 16 1 18 1 1 14 41 1 20 7 1 40 26 1 15 20 1 19 33 1 48 19 1 47 43 1 36 49 1 20 4 1 43 5 1 1 14 1 48 9 1 9 29 1 4 26 1 3 2 1 29 41 1 27 13 1 22 42 1 39 2 1 21 32 1 26 33 1 32 10 1 4 48 1 15 49 1 32 21 1 50 31 1 25 8 1 50 41 1 27 12 1 9 1 1 19 29 1 31 27 1 28 13 1 4 7 1 25 26 1 22 37 1 38 1 1 34 39 1 24 22 1 27 31 1 5 30 1 20 30 1 8 22 1 13 6 1 6 30 1 9 24 1 18 17 1 29 1 1 2 29 1 43 44 1 46 35 1 40 3 1 5 16 1 50 4 1 5 10 1 50 44 1 10 38 1 18 28 1 15 43 1 37 1 1 12 43 1 2 44 1 15 25 1 25 40 1 1 30 1 10 22 1 46 47 1 25 45 1 */

Compilation message (stderr)

merchant.cpp:43:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...