Submission #746391

#	Time	Username	Problem	Language	Result	Execution time	Memory
746391		kirakosyan	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	110 ms	4428 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);
using ll = long long;
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);
    }
}
vector<vector<pair<ll, ll>>>gp;
void solve() {
    ll n, m, k; cin >> n >> m >> k;
    gp = vector<vector<pair<ll, ll>>>(n);
    vector<vector<ll>>apr(n, vector<ll>(2 * k));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < 2 * k; j++) {
            cin >> apr[i][j];

        }
    }
    vector<vector<ll>>d(n, vector<ll>(n, 1e18)), max_delta(n, vector<ll>(n));
    for (ll i = 0; i < m; i++) {
        ll u, v, w; cin >> u >> v >> w;
        u--;
        v--;
        gp[u].push_back({ v,w });
        d[u][v] = w;
    }
    for (ll k = 0; k < n; k++) {
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            for (ll e = 0; e < 2 * k; e += 2) {
                if (apr[i][e] != -1 && apr[j][e + 1] != -1&&i!=j) {
                    max_delta[i][j] = max(apr[j][e+1] - apr[i][e], max_delta[i][j]);
                }
             } 
        }
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<n;j++){
    //          cout<<d[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    ll l=0,r=1e11;
     while(l+1<r){
        vector<vector<ll>> d1(n, vector<ll>(n, -1e18));
         ll a=0;
         ll mid=(l+r)/2;
         for(ll i=0;i<n;i++){
             for(ll j=0;j<n;j++){
                 ll a=1e18/mid;
                  d1[i][j]=max_delta[i][j]-mid*min(a, d[i][j]);
             }
         }
     for (ll k = 0; k < n; ++k) {
        for (ll i = 0; i < n; ++i) {
            for (ll j = 0; j < n; ++j) {
                d1[i][j] = max(d1[i][j], d1[i][k] + d1[k][j]);
            }
        }
    }
    for(ll i=0;i<n;i++)if(d1[i][i]>=0)a=1;
        if(a==1) l=mid;
         else r=mid;
    }
     cout<<l<<endl;
}


signed main() {
        FASTIO
        ll t=1;
        //cin >> t;
        while (t--) {
            solve();
        }
}

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