Submission #554123

#	Time	Username	Problem	Language	Result	Execution time	Memory
554123		status_coding	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	1088 ms	3280 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];

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)
{
    /*
    cout<<'\n';

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            long long nval = prof[i][j] - x * dist[i][j];
            cout<<nval<<' ';
        }
        cout<<'\n';
    }

    cout<<"\n\n";
    */

    for(int rad=1; rad<=n; rad++)
    {
        for(int i=1; i<=n; i++)
            profMax[i] = -1e18;

        profMax[rad] = 0;

        for(int nr=1; nr<n; nr++)
        {
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                {
                    if(i == j)
                        continue;

                    long long nval = prof[i][j] - x * dist[i][j];
                    nval += profMax[i];

                    if(nval > profMax[j])
                        profMax[j] = nval;
                }
        }

        for(int i=1;i<=n;i++)
        {
            if(i == rad)
                continue;

            long long nval = prof[i][rad] - x * dist[i][rad];
            nval += profMax[i];

            if(nval >= 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;

        dist[i][i] = 0;
    }


    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();

    //cout<<ok(3);
    //return 0;

    long long st=0, 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: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34