Submission #1171252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171252		Muhammet	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	207 ms	2192 KiB

merchant

#include "bits/stdc++.h"

using namespace std;

#define ll long long

const int N = 1e2 + 5;

vector <pair <int, int>> v[N];

ll n, m, k, ans = 1e9;

vector <vector <ll>> dis, e, b, s;

bool check(ll x) {
	e.assign(n+1, vector <ll> (n+1, 0));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int x = 1; x <= k; x++) {
				if(b[i][x] == -1 or s[j][x] == -1) continue;
				e[i][j] = max(e[i][j], (s[j][x] - b[i][x]));
			}
			e[i][j] -= (x * dis[i][j]);
			e[i][j] *= (-1);
		}
	}
	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				e[i][j] = min(e[i][j], e[i][x] + e[x][j]);
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(e[i][i] <= 0) return true;
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> k;
	b.assign(n+1, vector <ll> (k+1, 0)), s.assign(n+1, vector <ll> (k+1, 0));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++) {
			cin >> b[i][j] >> s[i][j];
		}
	}

	dis.assign(n+1, vector <ll> (n+1, 1e15)); 

	for(int i = 1; i <= m; i++) {
		int u1, u2, w;
		cin >> u1 >> u2 >> w;
		v[u1].push_back({u2, w});
		dis[u1][u2] = 2;
	}

	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
			}
		}
	}

	int l = 0, r = 1e9;
	while(l <= r) {
		int md = (l + r) / 2;
		if(check(md)) {
			l = md+1;
			ans = md;
		}
		else {
			r = md-1;
		}
	}

	cout << ans;

	return 0;
}

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