Submission #746520

#	Time	Username	Problem	Language	Result	Execution time	Memory
746520		harut_13	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	101 ms	4280 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   endl 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = pv(a, b / 2);
    if (b % 2) {
        return (res * res) * a;
    }
    else {
        return (res * res);
    }
}
void solve() {
    ll n, m, k;
    cin >> n >> m >>k;
    vector<vecl> arn(n, vecl(k));
    vector<vecl> cax(n, vecl(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            ll a, c; cin >> a >> c;
            arn[i][j] = a;
            cax[i][j] = c;
        }
    }
    vector<vector<pii>> gp(n);
    vector<vecl> d(n, vecl(n,1e18));
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        gp[--u].pshb({--v,w });
        d[u][v] = w;
    }
    vector<vecl> delta(n, vecl(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k1 = 0; k1 < k; k1++) {
                if(arn[i][k1]!=-1 && cax[j][k1]!=-1)delta[i][j] = max(delta[i][j],  cax[j][k1] - arn[i][k1]);
            }
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    ll l = 0, r = 1e11;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        vector<vecl> d1(n, vecl(n,0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long long b = 1e18 / m;
                d1[i][j] = delta[i][j] - m * min(b, d[i][j]);
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d1[i][j] = max(d1[i][j], d1[i][k] + d1[k][j]);
                }
            }
        }
        bool f = false;
        for (int i = 0; i < n; i++) {
            if (d1[i][i] >= 0)f = true;
        }
        if (f)l = m;
        else r = m;
    }
    cout << l << endl;   
}

int main() {
    FASTIO

       // int t; cin >> t;
         //while (t--)
        solve();
}

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