Submission #904009

#	Time	Username	Problem	Language	Result	Execution time	Memory
904009		vjudge1	Travelling Merchant (APIO17_merchant)	C++17	33 / 100	68 ms	5596 KiB

merchant

#include "bits/stdc++.h"
using namespace std;
#define Mucho LLONG_MAX / 2
long long N, M, K;
vector< vector<long long> > Compra, Venta, Grafo1, Ganancia, Grafo2;
void Floyd_Warshall(vector< vector<long long> > &Grafo){
    for(long long i = 0; i < N; i++) for(long long j = 0; j < N; j++) for(long long k = 0; k < N; k++) Grafo[j][k] = min(Grafo[j][k], Grafo[j][i] + Grafo[i][k]);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M>>K;
    vector<long long> a(N, Mucho);
    vector<long long> b(K, Mucho);
    vector<long long> c(N, 0);
    Grafo1.assign(N, a);
    Grafo2.assign(N, a);
    Compra.assign(N, b);
    Venta.assign(N, b);
    Ganancia.assign(N, c);
    for(long long i = 0; i < N; i++) for(long long j = 0; j < K; j++) cin>>Compra[i][j]>>Venta[i][j];
    for(long long i = 0; i < M; i++){
        long long V, W, T;
        cin>>V>>W>>T;
        Grafo1[V - 1][W - 1] = T;
    }
    Floyd_Warshall(Grafo1);
    for(long long i = 0; i < N; i++) for(long long j = 0; j < N; j++) for(long long k = 0; k < K; k++) if(Venta[j][k] != -1 and Compra[i][k] != -1) Ganancia[i][j] = max(Ganancia[i][j], Venta[j][k] - Compra[i][k]);
    long long Inicio = 0;
    long long Final = 1e9;
    while(Inicio <= Final){
        long long Promedio = (Inicio + Final) / 2;
        for(long long i = 0; i < N; i++) for(long long j = 0; j < N; j++) Grafo2[i][j] = Promedio * min(Grafo1[i][j], Mucho / Promedio) - Ganancia[i][j];
        Floyd_Warshall(Grafo2);
        bool Ciclo_positivo = 0;
        for(long long i = 0; i < N; i++) if(Grafo2[i][i] <= 0) Ciclo_positivo = 1;
        if(Ciclo_positivo) Inicio = Promedio + 1;
        else Final = Promedio - 1;
    }
    cout<<Final;
    return 0;
}

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