Submission #571091

#	Time	Username	Problem	Language	Result	Execution time	Memory
571091		YouAreMyGalaxy	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	100 ms	3336 KiB

merchant

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e2, K = 1e3, oo = 2e9;
int d[N + 1][N + 1], prof[N + 1][N + 1];
int n, m, k, b[N + 1][K + 1], s[N + 1][K + 1];
long long dp[N + 1][N + 1];
void read()
{
    cin >> n >> m >> k;
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; ++ i)
    {
        //d[i][i] = 0;
        for (int j = 1; j <= k; ++ j)
        {
            cin >> b[i][j] >> s[i][j];
        }
    }
    for (int i = 1; i <= m; ++ i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
    }
}
bool check(int x)
{
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            dp[i][j] =  prof[i][j] - 1LL * x * d[i][j];
            //cerr << dp[i][j] << ' ';
        }
        //cerr << '\n';
    }
    for (int k = 1; k <= n; ++ k)
    {
        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= n; ++ j)
            {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    /*cerr << '\n';
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            cerr << dp[i][j] << ' ';
        }
        cerr << '\n';
    }*/
    for (int i = 1; i <= n; ++ i)
    {
        if (dp[i][i] >= 0)
        {
            return true;
        }
    }
    return false;
}
void solve()
{
    for (int k = 1; k <= n; ++ k)
    {
        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= n; ++ j)
            {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            prof[i][j] = 0;
            for (int l = 1; l <= k; ++ l)
            {
                if (b[i][l] < 0 || s[j][l] < 0)
                {
                    continue;
                }
                prof[i][j] = max(prof[i][j], s[j][l] - b[i][l]);
            }
        }
    }
    int low = 1, high = 1e9;
    while(low <= high)
    {
        int mid = (low + high)/2;
        if (check(mid))
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    cout << high;
    //cout << check(2);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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