oj.uz

Submission #89876

# Submission time Handle Problem Language Result Execution time Memory
89876 2018-12-18T17:48:04 Z Alexa2001 Travelling Merchant (APIO17_merchant) C++17
0 / 100
 82 ms 3064 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 105, Kmax = 1005;
const ll inf = 1e18;

int buy[Nmax][Kmax], sell[Nmax][Kmax];
int profit[Nmax][Nmax];
ll dist[Nmax][Nmax], dp[Nmax][Nmax];
int n, m, k;

void read()
{
    int i, j, t, tmp;
    cin >> n >> m >> k;

    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=k; ++j) cin >> buy[i][j];
        for(j=1; j<=k; ++j) cin >> sell[i][j];
    }

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            dist[i][j] = (i == j ? 0 : inf);

    int x, y;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y >> tmp;
        dist[x][y] = tmp;
    }

    for(t=1; t<=n; ++t)
        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)
                dist[i][j] = min(dist[i][t] + dist[t][j], dist[i][j]);

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            for(t=1; t<=k; ++t)
                if(sell[j][t] != -1 && buy[i][t] != -1)
                    profit[i][j] = max(profit[i][j], sell[j][t] - buy[i][t]);
}

bool check(int E)
{
    int i, j, t;

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            if(i == j) dp[i][j] = 0;
                else if((long double) dist[i][j] * E <= inf)
                    dp[i][j] = profit[i][j] - (ll) dist[i][j] * E;
                else dp[i][j] = -inf;

    for(t=1; t<=n; ++t)
        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)
                dp[i][j] = max(dp[i][j], dp[i][t] + dp[t][j]);

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            if(i != j && dp[i][j] + dp[j][i] >= 0) return 1;
    return 0;
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    read();
    int ans = 0, step;

    for(step = (1<<29); step; step >>= 1)
        if(check(ans + step)) ans += step;

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

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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