Submission #549087

#	Time	Username	Problem	Language	Result	Execution time	Memory
549087		status_coding	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	69 ms	2516 KiB

merchant

#include <iostream>

using namespace std;

long long n,k,m;

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

long long dist[105][105];
long long val[105][105];

long long distMax[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 calcProfit()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n ; j++)
        {
            if(i == j)
                continue;

            val[i][j] = 0;

            for(int produs=1; produs<=k; produs++)
                val[i][j] = max(val[i][j], -buy[i][produs] + sell[j][produs]);
        }
}

bool ok(long long x)
{
    distMax[1] = 0;
    for(int i=2;i<=n;i++)
        distMax[i] = -1e18;

    int aux = n;
    while(aux)
    {
        aux --;

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

                long long l = val[i][j] - dist[i][j] * x;

                if(distMax[j] < distMax[i] + l)
                {
                    if(!aux)
                        return true;

                    distMax[j] = distMax[i] + l;
                }
            }
    }

    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];

            if(buy[i][j] == -1)
                buy[i][j] = 1e9;

            if(sell[i][j])
                sell[i][j] = - 1e9;
        }
    }

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

            dist[i][j] = 1e9;
        }

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

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

    calcDist();
    calcProfit();

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<dist[i][j]<<' ';
        cout<<'\n';
    }
    return 0;

    long long st, dr, mij, last=0;
    st=0;
    dr=1e9;

    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