#include <bits/stdc++.h>
#define int long long
using namespace std;
vector < vector < pair < int, int > > > adj;
vector < vector < int > > b;
vector < vector < int > > s;
vector < pair < int, vector < int > > > cicles;
vector < bool > visited;
void dfs(int u, int minutes, vector < int >& cicle) {
visited[u] = true;
for (pair < int, int > p : adj[u]) {
int v = p.first, d = p.second;
if (!visited[v]) {
cicle.push_back(v);
dfs(v, minutes + d, cicle);
cicle.pop_back();
visited[v] = false;
} else if (v == 0) {
cicles.push_back(make_pair(minutes + d, cicle));
}
}
}
signed main()
{
int n, m, k;
cin >> n >> m >> k;
b = s = vector < vector < int > >(n, vector < int >(k));
for (int i = 1; i < n; ++i) {
for (int j = 0; j < k; ++j) {
cin >> b[i][j] >> s[i][j];
}
}
adj = vector < vector < pair < int, int > > >(n);
while (m--) {
int u, v, d;
cin >> u >> v >> d;
--u; --v;
adj[u].push_back(make_pair(v, d));
}
vector < int > profit(n, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
if (s[i][j] != -1) profit[i] = max(profit[i], s[i][j] - b[0][j]);
}
}
vector < int > cicle = {0};
visited = vector < bool >(n, false);
dfs(0, 0, cicle);
int ans = 0;
for (pair < int, vector < int > > p : cicles) {
int t = p.first, max_profit = 0;
for (int i : p.second) {
max_profit = max(max_profit, profit[i]);
}
if (t > 0) ans = max(ans, max_profit / t);
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
41 ms |
3528 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
856 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |