Submission #135324

#	Time	Username	Problem	Language	Result	Execution time	Memory
135324		emaborevkovic	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	155 ms	5240 KiB

merchant

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define pb push_back
#define mp make_pair
#define TRACE(x) cerr << #x << " " << x << endl
typedef long long ll;

ll n,m,k;
pair <ll, ll> c[105][10005];
vector <pair <int, ll> > ceste[105];
ll floyd[105][105];
vector <pair <ll, pair<ll, ll> > > ls[105];
ll pink[105][105];

bool func (ll x) {
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++) {
			pink[i][j] = 1e13;
		}
	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<ls[i].size();j++) {
			pink[i][ls[i][j].first] = ls[i][j].second.second;
			ll oduzmi = ls[i][j].second.first*x;
			pink[i][ls[i][j].first] -= oduzmi;
			pink[i][ls[i][j].first] *= -1;
		}
		pink[i][i] = 1;
	}
	for (int l=0;l<n;l++) {
		for (int i=0;i<n;i++) {
			for (int j=0;j<n;j++) {
				if (pink[i][j] > pink[i][l] + pink[l][j]) {
					pink[i][j] = pink[i][l] + pink[l][j];
				}
			}
		}
	}
	for (int i=0;i<n;i++) {
		if (pink[i][i] <= 0) return 1;
	}
	return 0;
}

int main() {
	cin >> n >> m >> k;
	for (int i=0;i<n;i++) {
		for (int j=0;j<k;j++) {
			scanf("%lld%lld", &c[i][j].first, &c[i][j].second);
		}
	}
	for (int i=0;i<m;i++) {
		ll a1,a2,a3;
		scanf("%lld%lld%lld", &a1, &a2, &a3);
		a1--;
		a2--;
		ceste[a1].pb(mp(a2, a3));
	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++) floyd[i][j] = 1e9+5;
	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<ceste[i].size();j++) {
			floyd[i][ceste[i][j].first] = ceste[i][j].second;
		}
		floyd[i][i] = 0;
	}
	for (int l=0;l<n;l++) {
		for (int i=0;i<n;i++) {
			for (int j=0;j<n;j++) {
				if (floyd[i][j] > floyd[i][l] + floyd[l][j]) {
					floyd[i][j] = floyd[i][l] + floyd[l][j];
				}
			}
		}
	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++) {
			if (i == j) continue;
			if (floyd[i][j] == 1e9+5) continue;
			ll zarada = 0;
			for (int l=0;l<k;l++) {
				if (c[j][l].second == -1) continue;
				if (c[i][l].first == -1) continue;
				zarada = max(zarada, c[j][l].second - c[i][l].first);
			}
			ls[i].pb(mp(j, mp(floyd[i][j], zarada)));
		}
	}
	ll lo, hi, mid;
	lo = 0;
	hi = 1e9;
	while (lo < hi) {
		ll suma = lo+hi;
		mid = suma/2;
		if (suma % 2 == 1) mid++;
		if (func(mid)) lo = mid;
		else hi = mid-1;
	}
	cout << lo;
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'bool func(ll)':
merchant.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<ls[i].size();j++) {
                ~^~~~~~~~~~~~~
merchant.cpp: In function 'int main()':
merchant.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<ceste[i].size();j++) {
                ~^~~~~~~~~~~~~~~~
merchant.cpp:53:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &c[i][j].first, &c[i][j].second);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a1, &a2, &a3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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