제출 #404719

#제출 시각아이디문제언어결과실행 시간메모리
404719fadi57여행하는 상인 (APIO17_merchant)C++14
0 / 100
68 ms1860 KiB
#include<bits/stdc++.h> using namespace std; const int mx=200; typedef long long ll; int inf=1e9+10; const int mod=1e9+7; int n,m,k; vector<pair<ll,ll>>v[mx]; vector<pair<ll,ll>>adj[mx]; ll best[mx]; int vis[mx];ll ans=0; void dfs(int node,ll t,ll sfar){ // cout<<node<<"\n "; vis[node]=1; sfar=max(sfar,best[node]); for(auto it:adj[node]){ //cout<<it.first<<" "; if(it.first==0){ //cout<<"test \n"<<sfar<<endl; t+=it.second; ans=max(ans,sfar/t); }else if(!vis[it.first]){ dfs(it.first,t+it.second,sfar); } } return ; } int main(){ cin>>n>>m>>k; for(int i=0;i<n;i++){ for(int j=0;j<k;j++){ ll x,y; cin>>x>>y; if(i!=0){ best[i]=max(best[i],y-v[0][j].first); }else{ best[i]=max(best[i],y-x); } v[i].push_back({x,y}); } } for(int i=0;i<m;i++){ ll x,y,w; cin>>x>>y>>w; x--;y--; adj[x].push_back({y,w}); } for(int i=0;i<n;i++){ dfs(0,0,0); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...