Submission #404729

#	Time	Username	Problem	Language	Result	Execution time	Memory
404729		fadi57	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	67 ms	1860 KiB

merchant

#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(y>=0){
        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;
 }

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34