Submission #1245238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245238		Thunnus	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	19 ms	2112 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int> 
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int INF = LLONG_MAX / 2;

inline void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vvi dist(n + 1, vi(n + 1, INF));
    vvi b(n + 1, vi(k + 1)), s(n + 1, vi(k + 1));
    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 < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        dist[a][b] = min(dist[a][b], w);
    }
    
    auto floyd_warshall = [&](vvi &dist) -> void {
        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]);
                }
            }
        }
        /*cout << "dist: \n";
        for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				cout << dist[i][j] << " ";
			}
			cout << "\n";
		}*/
        return; 
    };
    floyd_warshall(dist);

    vvi profit(n + 1, vi(n + 1));
    for(int i = 1; i <= n; i++){ // find the maximum profit of each path
        for(int j = 1; j <= n; j++){
            for(int x = 1; x <= k; x++){
                if(s[j][x] == -1 || b[i][x] == -1) continue;
                profit[i][j] = max(profit[i][j], s[j][x] - b[i][x]);
            }
        }
    }

    // ratios are inconvenient, so let's consider a simpler problem: given R, can we find a profit cycle with profit P and time T such that P / T >= R
    // This is convenient because we can make it linear: this problem is equivalent to checking whether we can find a profit cycle with profit P and time T such that P - TR >= 0
    // If we weight each edge as p - tR, this is equivalent to checking whether a non-negative cycle exists in the graph.
    // weight as tR - p (0 >= TR - P) and look for a negative cycle
    // R is valid if R + 1 is valid -> binary search

    auto check = [&](int r) -> bool {
        vvi new_dist(n + 1, vi(n + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                new_dist[i][j] = min(dist[i][j], INF / r) * r - profit[i][j];
            }
        }
        floyd_warshall(new_dist);
        for(int i = 1; i <= n; i++){
            if(new_dist[i][i] <= 0) return true;
        }
        return false;
    };

    auto bs = [&]() -> int {
        int lo = 1, hi = 5, ret = lo, mid;
        while(hi >= lo){
            mid = lo + (hi - lo) / 2;
            if(check(mid)){
                ret = mid;
                lo = mid + 1;
            }
            else{
                hi = mid - 1;
            }
        }
        return ret;
    };

    cout << bs() << "\n";
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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