Submission #554159

#	Time	Username	Problem	Language	Result	Execution time	Memory
554159		status_coding	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	150 ms	4304 KiB

merchant

#include <iostream>
#pragma GCC optimize ("unroll-loops")

using namespace std;

long long n,m,k;

long long dist[105][105];

long long buy[105][1005], sell[105][1005];
long long prof[105][105];

long long profMax[105][105];

void calcDist()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

void calcProf()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            prof[i][j] = 0;

            for(int nr=1; nr<=k; nr++)
                if(buy[i][nr] != -1 && sell[j][nr] != -1)
                    prof[i][j] = max(prof[i][j], sell[j][nr] - buy[i][nr]);
        }
}

bool ok(long long x)
{
    long long inf = 1e18;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            profMax[i][j] = x * min(dist[i][j], inf / x) - prof[i][j];

    for(int k=1; k<=n; k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                profMax[i][j] = min(profMax[i][j], profMax[i][k] + profMax[k][j]);

    for(int i=1;i<=n;i++)
        if(profMax[i][i] <= 0)
            return true;

    return false;
}

int main()
{
    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];

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dist[i][j] = 1e18;

    for(int i=1; i<=m; i++)
    {
        long long x, y, w;
        cin>>x>>y>>w;

        dist[x][y] = min(dist[x][y], w);
    }

    calcDist();
    calcProf();

    long long st=1, dr=1e9, mij, last=0;
    while(st <= dr)
    {
        mij = (st+dr)/2;

        if(ok(mij))
        {
            last = mij;
            st = mij+1;
        }
        else
            dr = mij-1;
    }

    cout<<last;
    return 0;
}

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