Submission #739371

#	Time	Username	Problem	Language	Result	Execution time	Memory
739371		Magikarp4000	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	79 ms	6908 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#define int long long

const int MAXN = 1e2+1, MAXK = 1e3+1;
int n,m,K;
int b[MAXN][MAXK], s[MAXN][MAXK];
int dist[MAXN][MAXN], d[MAXN][MAXN], prof[MAXN][MAXN];
bool good[MAXN];
vector<pair<int,PII>> v[MAXN];

bool check(int val) {
    FOR(i,1,n+1) {
        FOR(j,1,n+1) {
            d[i][j] = LLINF;
        }
        d[i][i] = good[i] = 0;
    }
    FOR(i,1,n+1) {
        FOR(j,1,n+1) {
            if (i == j || dist[i][j] == LLINF) continue;
            d[i][j] = dist[i][j]*val-prof[i][j];
        }
    }
    FOR(k,1,n+1) {
        FOR(i,1,n+1) {
            FOR(j,1,n+1) { 
                if (d[i][k]+d[k][j] == 0 && i == j && j != k) good[i] = 1;
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
    // FOR(i,1,n+1) {
    //     FOR(j,1,n+1) cout << d[i][j] << ' ';
    //     cout << ln;
    // }
    // cout << ln;
    FOR(i,1,n+1) if (d[i][i] < 0 || good[i]) return 1;
    return 0;
}

signed main() {
    OPTM;
    cin >> n >> m >> K;
    FOR(i,1,n+1) {
        FOR(j,1,K+1) cin >> b[i][j] >> s[i][j];
    }
    FOR(i,1,n+1) {
        FOR(j,1,n+1) {
            dist[i][j] = LLINF;
            prof[i][j] = -1;
        }
        dist[i][i] = 0;
    }
    FOR(i,0,m) {
        int x,y,w; cin >> x >> y >> w;
        int mx = 0;
        FOR(j,1,K+1) 
        v[x].PB({y,{mx,w}});
        dist[x][y] = w;
    }
    FOR(k,1,n+1) {
        FOR(i,1,n+1) {
            FOR(j,1,n+1) { 
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    FOR(i,1,n+1) {
        FOR(j,1,n+1) {
            FOR(x,1,K+1) {
                if (dist[i][j] == LLINF) continue;
                int mx = 0;
                if (s[j][x] != -1 && b[i][x] != -1) mx = max(mx, s[j][x]-b[i][x]);
                prof[i][j] = mx;
            }
        }
    }
    int l = 1, r = 1LL*(1e12+1);
    while (l < r) {
        int mid = (l+r)/2;
        if (check(mid)) l = mid+1;
        else r = mid;
    }
    cout << l-1;
}

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