Submission #677342

#	Time	Username	Problem	Language	Result	Execution time	Memory
677342		MasterTaster	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	145 ms	4176 KiB

merchant

#include <iostream>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 110
#define MAXK 1010
#define INF 1000000000000000000LL

using namespace std;

int n, m, k;
ll b[MAXN][MAXK], s[MAXN][MAXK], dist[MAXN][MAXN], p[MAXN][MAXN], novi[MAXN][MAXN], ress;

void fw(ll d[MAXN][MAXN])
{
    for (int l=1; l<=n; l++)
    {
        for (int u=1; u<=n; u++)
        {
            for (int v=1; v<=n; v++)
            {
                d[u][v]=min(d[u][v], d[u][l]+d[l][v]);
            }
        }
    }
}

int main() {
    cin>>n>>m>>k;

    for (int i=1; i<=n; i++) for (int j=1; j<=k; j++) cin>>b[i][j]>>s[i][j];
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dist[i][j]=INF;

    for (int i=0; i<m; i++)
    {
        ll u, v, w; cin>>u>>v>>w;
        dist[u][v]=w;
    }
    fw(dist);
    /*for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
        }
    }*/

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            for (int l=1; l<=k; l++)
            {
                if (b[i][l]==-1 || s[j][l]==-1) continue;
                p[i][j]=max(p[i][j], s[j][l]-b[i][l]);
            }
            //cout<<i<<" "<<j<<" "<<p[i][j]<<endl;
        }
    }

    ll l=1, r=1000000000LL;
    while (l<=r)
    {
        ll mid=l+(r-l)/2;
        //cout<<mid<<endl;
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++)
        {
            //if (dist[i][j]==INF) novi[i][j]==INF-p[i][j];///-p
            novi[i][j]=min(dist[i][j], INF/mid)*mid-p[i][j];
        }
        fw(novi);
        bool moze=false;
        for (int i=1; i<=n; i++) if (novi[i][i]<=0) moze=true;

        if (moze)
        {
            ress=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    cout<<ress;


}

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