Submission #1281317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281317		Faisal_Saqib	Travelling Merchant (APIO17_merchant)	C++20	12 / 100	43 ms	1108 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=101,K=1001;
int b[N][K],s[N][K];
ll dist[N][N];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dist[i][j]=1e18;
        }
        dist[i][i]=0;
        for(int j=1;j<=k;j++)
        {
            cin>>b[i][j]>>s[i][j];
        }
    }
    for(int i=0;i<m;i++)
    {
        int v,w,t;
        cin>>v>>w>>t;
        dist[v][w]=min(dist[v][w],(ll)t);
    }
    for(int v=1;v<=n;v++)
    {
        for(int x=1;x<=n;x++)
        {
            for(int y=1;y<=n;y++)
            {
                dist[x][y]=min(dist[x][y],dist[x][v]+dist[v][y]);
            }
        }
    }
    ll ans=0;
    for(int e=1;e<=n;e++)
    {
        ll d=dist[1][e]+dist[e][1];
        if(d>0)
        {
            for(int j=1;j<=k;j++)
            {
                // let buy j at 1 and sell j at e
                if(s[e][j]!=-1)
                {
                    ans=max(ans,(s[e][j]-b[1][j])/d);
                }
            }
        }
    }
    cout<<ans<<endl;
}

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