Submission #677339

#	Time	Username	Problem	Language	Result	Execution time	Memory
677339		MasterTaster	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	130 ms	2136 KiB

merchant

#include <climits>
#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 LLONG_MAX/2

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=0, 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]=dist[i][j]*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;


}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:72:44: warning: statement has no effect [-Wunused-value]
   72 |             if (dist[i][j]==INF) novi[i][j]==INF-p[i][j];///-p
      |                                  ~~~~~~~~~~^~~~~~~~~~~~~

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