oj.uz

Submission #123677

# Submission time Handle Problem Language Result Execution time Memory
123677 2019-07-02T03:49:36 Z nvmdava Travelling Merchant (APIO17_merchant) C++17
0 / 100
 104 ms 4632 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll d[105][105], p[105][105], t[105][105];
ll s[105][2005], b[105][2005];
int n, m, k;

inline void fw(ll re[105][105]){
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int l = 1; l <= n; l++)
				re[j][l] = min(re[j][l], re[j][i] + re[i][l]);
}

bool check(ll val){
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			t[i][j] = d[i][j] * val - p[i][j];
	
	fw(t);
	for(int i = 1; i <= n; i++){
		if(t[i][i] <= 0) return 1;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			d[i][j] = 100000000000;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++){
			cin>>b[i][j]>>s[i][j];
		}
	}
	
	while(m--){
		int v, u, t;
		cin>>v>>u>>t;
		d[v][u] = t;
	}
	fw(d);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(d[i][j] == 100000000000)
				continue;
			for(int l = 1; l <= k; l++){
				if(b[i][l] == -1 || s[j][l] == -1) continue;
				p[i][j] = max(p[i][j], s[j][l] - b[i][l]);
			}
		}
	}
	
	long long l = 0, r = 100000000000;
	while(l != r){
		ll m = (l + r + 1) >> 1;
		if(check(m)) l = m;
		else r = m - 1;
	}
	cout<<l;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 888 KB Output is correct
2 Correct 9 ms 888 KB Output is correct
3 Correct 10 ms 1144 KB Output is correct
4 Correct 9 ms 1004 KB Output is correct
5 Correct 10 ms 1016 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 9 ms 940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1764 KB Output is correct
2 Correct 104 ms 4632 KB Output is correct
3 Correct 51 ms 1604 KB Output is correct
4 Incorrect 54 ms 1756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 888 KB Output is correct
2 Correct 9 ms 888 KB Output is correct
3 Correct 10 ms 1144 KB Output is correct
4 Correct 9 ms 1004 KB Output is correct
5 Correct 10 ms 1016 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 9 ms 940 KB Output isn't correct
8 Halted 0 ms 0 KB -