# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
104086 | 2019-04-04T00:23:27 Z | autumn_eel | Travelling Merchant (APIO17_merchant) | C++14 | 826 ms | 2424 KB |
#include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<(n);i++) #define INF 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; int n,m,K; ll d[200][200],a[200][200]; int b[200][2000],s[200][2000]; bool C(ll t){ rep(i,n)rep(j,n)a[i][j]=-INF; rep(i,n)rep(j,n){ if(i==j)continue; rep(k,K){ if(b[i][k]==-1||s[j][k]==-1||d[i][j]==INF)continue; a[i][j]=max(a[i][j],max(0,s[j][k]-b[i][k])-t*d[i][j]); } } rep(k,n)rep(i,n)rep(j,n){ a[i][j]=max(a[i][j],a[i][k]+a[k][j]); } rep(i,n){ if(a[i][i]>=0)return true; } return false; } int main(){ cin>>n>>m>>K; rep(i,n)rep(j,K)scanf("%d%d",&b[i][j],&s[i][j]); memset(d,0x3f,sizeof(d)); rep(i,n)d[i][i]=0; rep(i,m){ int a,b,c;scanf("%d%d%d",&a,&b,&c);a--;b--; d[a][b]=c; } rep(k,n)rep(i,n)rep(j,n){ d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } ll l=0,r=INT_MAX; while(r-l>1){ ll t=(l+r)/2; if(C(t))l=t; else r=t; } cout<<l<<endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 289 ms | 2424 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1152 KB | Output is correct |
2 | Incorrect | 8 ms | 1152 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 117 ms | 1664 KB | Output is correct |
2 | Correct | 826 ms | 2424 KB | Output is correct |
3 | Correct | 77 ms | 1656 KB | Output is correct |
4 | Correct | 123 ms | 1664 KB | Output is correct |
5 | Correct | 144 ms | 1756 KB | Output is correct |
6 | Correct | 77 ms | 1692 KB | Output is correct |
7 | Correct | 18 ms | 1152 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 18 ms | 1152 KB | Output is correct |
10 | Correct | 23 ms | 1152 KB | Output is correct |
11 | Correct | 25 ms | 1152 KB | Output is correct |
12 | Correct | 10 ms | 1152 KB | Output is correct |
13 | Correct | 10 ms | 1152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1152 KB | Output is correct |
2 | Incorrect | 8 ms | 1152 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |