Submission #1112163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112163		kh0i	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	93 ms	4176 KiB

merchant

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 103;
const ll INF = 1e16;

int n, m, k;
ll b[N][N * 10], s[N][N * 10];
ll dist[N][N], c[N][N], f[N][N];

#define floyd(dak) for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) dak[i][j] = min(dak[i][j], dak[i][k] + dak[k][j]);

void solve(){
    cin >> n >> m >> k;

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= k; ++j)
            cin >> b[i][j] >> s[i][j];
        for(int j = 1; j <= n; ++j)
            dist[i][j] = INF;
    }

    for(int i = 1; i <= m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    floyd(dist);

    for(int u = 1; u <= n; ++u)
        for(int v = 1; v <= n; ++v)
            for(int j = 1; j <= k; ++j)
                if(b[u][j] != -1 and s[v][j] != -1)
                    c[u][v] = max(c[u][v], s[v][j] - b[u][j]);


    ll l = 1, r = 1e9, res = 0;
    while(l <= r){
        ll mid = (l + r) >> 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                f[i][j] = mid * min(INF / mid, dist[i][j]) - c[i][j];
        floyd(f);
        bool ok = 0;
        for(int i = 1; i <= n; ++i)
            if(f[i][i] <= 0)
                ok = 1;
        if(ok)
            res = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    cout << res;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int32_t main()':
merchant.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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