Submission #739338

#	Time	Username	Problem	Language	Result	Execution time	Memory
739338		Magikarp4000	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	93 ms	1964 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 d[MAXN][MAXN];
bool good[MAXN];
vector<pair<int,PII>> v[MAXN];
//vector<PII> v1[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) {
        FORX(u,v[i]) {
            d[i][u.F] = u.S.S*val-u.S.F;
        }
    }
    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,0,m) {
        int x,y,w; cin >> x >> y >> w;
        int mx = -LLINF;
        FOR(j,1,k+1) if (s[y][j] != -1 && b[x][j] != -1) mx = max(mx, s[y][j]-b[x][j]);
        if (mx != LLINF) v[x].PB({y,{mx,w}});
    }
    int l = 0, r = 1LL*(1e12+1);
    while (l < r) {
        int mid = (l+r)/2;
        if (check(mid)) l = mid+1;
        else r = mid;
    }
    cout << l;
}

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