# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101991 | bakpark | Travelling Merchant (APIO17_merchant) | C++14 | 147 ms | 2040 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
#include <limits.h>
using namespace std;
#define INF ((LLONG_MAX)>>10)
#define ll long long
int N,M,K;
ll B[101][1001];
ll S[101][1001];
ll T[101][101];
ll tval[101][101];
bool f(ll m){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
tval[i][j] = -INF;
if(T[i][j] == 0 ) continue;
for(int k = 1;k<=K;k++){
bool TF = S[j][k]==-1||B[i][k]==-1;
ll l=0,r=0;
if(!TF&&S[j][k]>B[i][k]){
l = S[j][k];
r = B[i][k];
}
tval[i][j] = max(tval[i][j],l-r-T[i][j]*m);
}
}
}
for(int k=1;k<=N;k++){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
tval[i][j] = max(tval[i][j],tval[i][k]+tval[k][j]);
}
}
}
for(int i=1;i<=N;i++){
if(tval[i][i]>=0) return true;
}
return false;
}
int main(){
scanf("%d %d %d",&N,&M,&K);
for(int i=1;i<=N;i++){
for(int j=0;j<K+K;j++){
ll tmp;scanf("%lld",&tmp);
if(j&1) S[i][j/2+1] = tmp;
else B[i][j/2+1] = tmp;
}
}
for(int i=0;i<M;i++){
int a,b;
ll c;
scanf("%d %d %lld",&a,&b,&c);
T[a][b] = c;
}
ll l = 0,r = 1000000000,answ=0;
while(l<=r){
ll m = (l+r)>>1;
if(f(m)){
l = m+1;
answ = m;
}
else r = m-1;
}
printf("%lld",answ);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |