Submission #57828

#	Time	Username	Problem	Language	Result	Execution time	Memory
57828		Jeez	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	99 ms	2168 KiB

merchant

#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e10;
const int MAX_N = 100 + 9;
const int MAX_K = 1000 + 9;
int n, m, K;
ll buy[MAX_N][MAX_K], sell[MAX_N][MAX_K];
ll w[MAX_N][MAX_N], dist[MAX_N][MAX_N], profit[MAX_N][MAX_N];
ll g[MAX_N][MAX_N], g2[MAX_N][MAX_N];

void read(){
    cin >> n >> m >> K;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= K; j++)
            cin >> buy[i][j] >> sell[i][j];

    for(int i = 0; i < m; i++){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }
}

void init(){
    for(int i = 1; i < MAX_N; i++)
        for(int j = 1; j < MAX_N; j++)
            dist[i][j] = INF;
}

void floyd(){
    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]);
}

bool check(ll rat){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            g[i][j] = -INF;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(dist[i][j] < INF)
                g[i][j] = max(g[i][j], profit[i][j] - dist[i][j] * rat);

    ll res = -INF;
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                g[i][j] = max(g[i][j], g[i][k] + g[k][j]);
                res = max(res, g[i][i]);
                if(res >= 0)
                    return true;
            }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            g2[i][j] = g[i][j];

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                g2[i][j] = max(g2[i][j], g2[i][k] + g2[k][j]);
                if(g2[i][j] > g[i][j])
                    return true;
            }

    return false;
}

void solve(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= K; k++)
                if(sell[j][k] == -1 || buy[i][k] == -1)
                    continue;
                else
                    profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);

    ll lo = 0, hi = 1e18, mid, ans = 0;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(check(mid)){
            ans = mid;
            lo = mid + 1;
        } else
            hi = mid - 1;
    }

    cout << ans << '\n';
}

int main()
{
    init();
    read();
    floyd();
    solve();
    return 0;
}

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