oj.uz

Submission #85077

# Submission time Handle Problem Language Result Execution time Memory
85077 2018-11-18T12:11:38 Z popovicirobert Travelling Merchant (APIO17_merchant) C++14
0 / 100
 129 ms 5384 KB 
#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]);
            }
        }
    }
    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] = -INF;
            for(i = 0; i <= k; i++) {
                if(buy[a][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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2680 KB Output is correct
2 Correct 44 ms 2680 KB Output is correct
3 Incorrect 44 ms 2824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2900 KB Output is correct
2 Correct 129 ms 4828 KB Output is correct
3 Correct 74 ms 4828 KB Output is correct
4 Correct 56 ms 5156 KB Output is correct
5 Correct 54 ms 5280 KB Output is correct
6 Correct 46 ms 5384 KB Output is correct
7 Correct 9 ms 5384 KB Output is correct
8 Correct 2 ms 5384 KB Output is correct
9 Correct 9 ms 5384 KB Output is correct
10 Incorrect 10 ms 5384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2824 KB Output isn't correct
2 Halted 0 ms 0 KB -