제출 #818052

#제출 시각아이디문제언어결과실행 시간메모리
818052Ozy여행하는 상인 (APIO17_merchant)C++17
100 / 100
71 ms4148 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define pll pair<lli,lli> #define MAX 100 #define INF (1ll<<60) lli n,m,k,res,a,b,c,prod; lli dis[MAX+2][MAX+2],profit[MAX+2][MAX+2],otro[MAX+2][MAX+2]; lli compras[MAX+2][1002],ventas[MAX+2][1002]; void floyd_warshall(lli g[MAX+2][MAX+2]) { rep(i,1,n) rep(j,1,n) rep(k,1,n) g[j][k] = min(g[j][k], g[j][i]+g[i][k]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> prod; rep(i,1,n) { rep(j,1,n) dis[i][j] = INF; rep(j,1,prod) cin >> compras[i][j] >> ventas[i][j]; } rep(i,1,m) { cin >> a >> b >> c; dis[a][b] = c; } floyd_warshall(dis); //si se pasa por referencia //defino el arreglo de profits con otro floyd_warshall rep(i,1,n) rep(j,1,n) rep(k,1,prod) { if(compras[i][k] == -1 || ventas[j][k] == -1) continue; profit[i][j] = max(profit[i][j], ventas[j][k] - compras[i][k]); } lli mitad,ini = 1; lli fin = (1ll<<30); while (ini <= fin) { mitad = (ini+fin)/2; rep(i,1,n) rep(j,1,n) otro[i][j] = mitad * min(dis[i][j], INF/mitad) - profit[i][j]; floyd_warshall(otro); bool ciclo_neg = false; rep(i,1,n) if(otro[i][i] <= 0) ciclo_neg = true; if (ciclo_neg) { ini = mitad + 1; res = mitad; } else fin = mitad-1; } cout << res; return 0; } //checar lo de pasar el arreglo por referencia
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...