Submission #85084

#	Time	Username	Problem	Language	Result	Execution time	Memory
85084		popovicirobert	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	115 ms	9848 KiB

merchant

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXN = 100;
const int MAXK = 1000;

int buy[MAXN + 1][MAXK + 1], sell[MAXN + 1][MAXK + 1];
ll dist[MAXN + 1][MAXN + 1], cst[MAXN + 1][MAXN + 1];
ll dp[MAXN + 1][MAXN + 1];

int n, m, k;

inline bool check(int delta) {
    int i, j;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            if(dist[i][j] < INF) {
                dp[i][j] = cst[i][j] - 1LL * dist[i][j] * delta;
            }
            else {
                dp[i][j] = -INF;
            }
        }
    }
    for(int a = 1; a <= n; a++) {
        for(int b = 1; b <= n; b++) {
            for(int c = 1; c <= n; c++) {
                dp[b][c] = max(dp[b][c], dp[b][a] + dp[a][c]);
                dp[b][c] = min(dp[b][c], INF);
            }
        }
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            if(i == j) {
                continue;
            }
            if(dp[i][j] + dp[j][i] >= 0) {
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    //ifstream cin("C.in");
    //ofstream cout("C.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= k; j++) {
            cin >> buy[i][j] >> sell[i][j];
        }
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            if(i == j) {
                dist[i][i] = 0;
                continue;
            }
            dist[i][j] = INF;
        }
    }
    for(i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }
    for(int a = 1; a <= n; a++) {
        for(int b = 1; b <= n; b++) {
            for(int c = 1; c <= n; c++) {
                dist[b][c] = min(dist[b][c], dist[b][a] + dist[a][c]);
            }
        }
    }
    for(int a = 1; a <= n; a++) {
        for(int b = 1; b <= n; b++) {
            cst[a][b] = 0;
            for(i = 1; i <= k; i++) {
                if(buy[a][i] > -1 && sell[b][i] > -1) {
                    cst[a][b] = max(cst[a][b], 1LL * sell[b][i] - buy[a][i]);
                }
            }
        }
    }
    int delta = 0;
    for(int step = 1 << 29; step; step >>= 1) {
        if(check(delta + step)) {
            delta += step;
        }
    }
    cout << delta;
    //cin.close();
    //cout.close();
    return 0;
}

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