Submission #1110678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110678		Icelast	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	68 ms	4432 KiB

merchant

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> buy(n+1, vector<ll>(k+1)), sell(n+1, vector<ll>(k+1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            cin >> buy[i][j] >> sell[i][j];
        }
    }
    vector<vector<ll>> adj(n+1, vector<ll>(n+1, INF));
    for(int i = 1; i <= m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u][v] = w;
    }
    vector<vector<ll>> just_profit(n+1, vector<ll>(n+1, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int v = 1; v <= k; v++){
                if(buy[i][v] != -1 && sell[j][v] != -1){
                    just_profit[i][j] = max(just_profit[i][j], sell[j][v]-buy[i][v]);
                }
            }
        }
    }
    vector<vector<ll>> shortest_path(n+1, vector<ll>(n+1, INF));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            shortest_path[i][j] = adj[i][j];
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                shortest_path[i][j] = min(shortest_path[i][j], shortest_path[i][k]+shortest_path[k][j]);
            }
        }
    }
    auto check = [&](ll x) -> bool{
        vector<vector<ll>> f(n+1, vector<ll>(n+1, -INF));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                f[i][j] = just_profit[i][j] - shortest_path[i][j]*x;
            }
        }
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    f[i][j] = max(f[i][j], f[i][k]+f[k][j]);
                }
            }
        }
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    if(f[i][j] < f[i][k] + f[k][j]){
                        return true;
                    }
                }
                if(f[i][i] >= 0){
                    return true;
                }
            }
        }
        return false;
    };
    ll l = 0, r = 1e9;
    while(l <= r){
        ll mid = (l+r)/2;
        if(check(mid)){
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    cout << l-1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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