Submission #488713

#	Time	Username	Problem	Language	Result	Execution time	Memory
488713		CyberSleeper	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	101 ms	4108 KiB

merchant

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define ld          long double
#define pii         pair<ll, ll>
#define pll         pair<ll, ll>
#define plii        pair<ll, pii>
#define nl          endl
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=250007, MOD=1e9+7, BLOCK=327, INF=1e9+7, INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

ll N, M, K, B[107][1007], S[107][1007], dist[107][107], dist2[107][107], profit[107][107];

bool bisa(ll x){
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            dist2[i][j]=-INF;
            if(dist[i][j]!=INF)
                dist2[i][j]=profit[i][j]-x*dist[i][j];
        }
    }
    bool ret=0;
    for(int k=1; k<=N; k++)
        for(int i=1; i<=N; i++)
            for(int j=1; j<=N; j++)
                dist2[i][j]=max(dist2[i][j], dist2[i][k]+dist2[k][j]);
    for(int i=1; i<=N; i++)
        if(dist2[i][i]>=0)
            return 1;
    return 0;
}

int main(){
    fastio;
    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=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            dist[i][j]=INF;
            profit[i][j]=0;
        }
    }
    for(ll u, v, w, i=0; i<M; i++){
        cin >> u >> v >> w;
        dist[u][v]=min(dist[u][v], w);
    }
    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]);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            for(int k=1; k<=K; k++)
                if(B[i][k]!=-1 && S[j][k]!=-1)
                    profit[i][j]=max(profit[i][j], S[j][k]-B[i][k]);
    ll le=1, ri=INF, mi;
    while(le<=ri){
        mi=(le+ri)/2;
        if(bisa(mi))
            le=mi+1;
        else
            ri=mi-1;
    }
    cout << le-1 << nl;
}

Compilation message (stderr)

merchant.cpp: In function 'bool bisa(long long int)':
merchant.cpp:32:10: warning: unused variable 'ret' [-Wunused-variable]
   32 |     bool ret=0;
      |          ^~~

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