Submission #974009

#	Time	Username	Problem	Language	Result	Execution time	Memory
974009		a_l_i_r_e_z_a	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	49 ms	2396 KiB

merchant

// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 100 + 5, maxk = 1000 + 5;
const ll inf = 1e18 + 7;
ll n, m, K, d[maxn][maxn], df[maxn][maxn], p[maxn][maxn];
ll b[maxn][maxk], s[maxn][maxk];

void floyd(ll adj[maxn][maxn]){
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++) smin(adj[i][j], adj[i][k] + adj[k][j]);
        }
    }
}

bool check(int mid){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            df[i][j] = mid * min(d[i][j], inf / mid) - p[i][j];
        }
    }
    floyd(df);
    for(int i = 0; i < n; i++) if(df[i][i] <= 0) return 1;
    return 0;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> K;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) d[i][j] = inf;
        for(int k = 0; k < K; k++) cin >> b[i][k] >> s[i][k];
    }
    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        d[u][v] = w;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < K; k++) if(b[i][k] > -1 && s[j][k] > -1){
                smax(p[i][j], s[j][k] - b[i][k]);
            }
        }
    }
    floyd(d);
    ll l = 0, r = 1e9 + 1;
    while(r - l > 1){
        ll mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l << '\n';

    return 0;
}

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