Submission #554177

#	Time	Username	Problem	Language	Result	Execution time	Memory
554177		QwertyPi	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	160 ms	2092 KiB

merchant

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 101, K = 1001;
const int inf = 1 << 30;
int d[N][N], p[N][N], rp[N][N];
int b[N][K], s[N][K];
int n, m, q;

bool check(int av){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			rp[i][j] = p[i][j] - av * d[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				rp[j][k] = max(rp[j][k], rp[j][i] + rp[i][k]);
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		if(rp[i][i] >= 0) return true;
	}
	return false;
}

int32_t main(){
	cin >> n >> m >> q;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < q; j++){
			cin >> b[i][j] >> s[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			d[i][j] = inf;
		}
	}
	for(int i = 0; i < m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;
		d[u][v] = min(d[u][v], w);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < q; k++){
				if(s[j][k] != -1 && b[i][k] != -1) p[i][j] = max(p[i][j], s[j][k] - b[i][k]);
			}
		}
	}
	
	int l = 0, r = 1e9;
	while(l != r){
		int mid = (l + r + 1) / 2;
		if(check(mid)){
			l = mid;
		}else{
			r = mid - 1;
		}
	}
	cout << l << endl;
}

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