Submission #89881

#	Time	Username	Problem	Language	Result	Execution time	Memory
89881		Alexa2001	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	117 ms	9648 KiB

merchant

#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] >> 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]);
                if(dp[i][j] > inf) return 1;
            }

    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: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34