제출 #968899

#제출 시각아이디문제언어결과실행 시간메모리
968899kilkuwu여행하는 상인 (APIO17_merchant)C++17
100 / 100
75 ms4320 KiB
#include <bits/stdc++.h> #define nl '\n' #ifdef LOCAL #include "template/debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M, K; std::cin >> N >> M >> K; constexpr int64_t inf = 1e18; int64_t B[N][K], S[N][K], d[N][N], p[N][N], cost[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = inf; } } for (int i = 0; i < N; i++) { for (int j = 0; j < K; j++) { std::cin >> B[i][j] >> S[i][j]; } } for (int i = 0; i < M; i++) { int u, v, c; std::cin >> u >> v >> c; --u, --v; d[u][v] = std::min(d[u][v], (int64_t) c); } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]); } } } dbg("done floyd") for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { p[i][j] = 0; // not doing shit for (int k = 0; k < K; k++) { if (B[i][k] != -1 && S[j][k] != -1) { p[i][j] = std::max(p[i][j], S[j][k] - B[i][k]); } } } } dbg("done profit"); int lb = 0, rb = 1e9; while (lb < rb) { int mb = (lb + rb + 1) / 2; dbg(mb); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cost[i][j] = std::min(inf / mb, d[i][j]) * mb - p[i][j]; } } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k][j]); } } } bool good = 0; for (int i = 0; i < N; i++) { good |= cost[i][i] <= 0; } if (good) { lb = mb; } else { rb = mb - 1; } } std::cout << lb << nl; // profit / time >= mid // profit - time * mid >= 0 // a neg loop }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...