Submission #119023

#	Time	Username	Problem	Language	Result	Execution time	Memory
119023		MAMBA	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	129 ms	2756 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

inline void read() {}
template <class S>
inline void read(S &arg) {
	cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
	while (Lptr != Rptr) {
		read(*Lptr);
		Lptr++;
	}
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
	read(arg);
	read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
	cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char del = ' ') {
	if (Lptr != Rptr) {
		write(*Lptr);
		Lptr++;
	}
	while (Lptr != Rptr) {
		write(del);
		write(*Lptr);
		Lptr++;
	}
}
template <class S, class... T>
inline void write(S arg, T... rest) {
	write(arg);
	write(' ');
	write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
	return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
	return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 110;
constexpr int K = 1010;

template <typename T>
inline T mod(T &v) {
	return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
	return mod(l += r);
}

ll po(ll v, ll u) {
	return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

int n , m , k;
ll B[N][K];
ll S[N][K];
ll mat[N][N];
ll dist[N][N];
ll d[N][N];


int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dist, 63 , sizeof(dist));
	read(n , m, k);

	rep(i , 0 , n) {
		dist[i][i] = 0;
		rep(j , 0 , k)
			read(B[i][j] , S[i][j]);
	}

	rep(i , 0 , m) {
		int u , v , w;
		read(u , v , w);
		u--, v--;
		smin(dist[u][v] , w);
	}

	rep(z , 0 , n) 
		rep(i , 0 , n)
		rep(j , 0 , n)
		smin(dist[i][j] , dist[i][z] + dist[z][j]);

	rep(i , 0 , n) {
		rep(j , 0 , n)
			rep(z , 0 , k)
			if (~B[i][z] && ~S[j][z])
				smax(mat[i][j] , S[j][z] - B[i][z]);
	}


	auto f = [](int limit) -> bool {

		memset(d , 63 , sizeof(d));

		rep(i , 0 , n)
			rep(j , 0 , n)
			if (dist[i][j] != dist[N - 1][N - 1]) 
				d[i][j] = dist[i][j] * limit - mat[i][j];


		rep(z , 0 , n)
			rep(i , 0 , n)
			rep(j , 0 , n)
				if (d[i][z] != d[N- 1][N - 1] &&
					d[z][j] != d[N - 1][N - 1]) {
					ll tmp = max(ll(-2e18) , d[i][z] + d[z][j]);
					smin(d[i][j] , tmp);
				}

		rep(i , 0 , n)
			rep(j , i + 1, n)
			if (d[i][j] + d[j][i] <= 0)
				return true;
		return false;

	};


	int lo = 0, hi = 2e9 + 10;
	while (lo != hi - 1) {
		int mid = lo + hi >> 1;
		if (f(mid))
			lo = mid;
		else
			hi = mid;
	}
	write(lo);

	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int32_t main()':
merchant.cpp:159:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~

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