# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
102000 | 2019-03-21T11:57:03 Z | bakpark | Travelling Merchant (APIO17_merchant) | C++14 | 125 ms | 2168 KB |
#include <cstdio> #include <algorithm> #include <limits.h> #include <memory.h> using namespace std; #define ll long long int N,M,K; ll B[101][1001], S[101][1001], T[101][101],val[101][101]; ll Q[101][101]; ll dist[101][101]; ll g(int st,int en,ll m,ll d){ return Q[st][en]-d*m; } bool f(ll m){ for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ if(T[i][j]) { dist[i][j] = T[i][j]; val[i][j] = g(i,j,m,T[i][j]); } else { dist[i][j] = -1; val[i][j] = LLONG_MIN; } } } for(int mid=1;mid<=N;mid++){ for(int st=1;st<=N;st++){ for(int en=1;en<=N;en++){ if(dist[st][mid]==-1||dist[mid][en]==-1) continue; ll td = dist[st][mid]+dist[mid][en]; ll hval = max(g(st,en,m,td),val[st][mid]+val[mid][en]); if(hval>val[st][en]){ dist[st][en] = td; val[st][en] = hval; } } } for(int n=1;n<=N;n++){ if(val[n][n]>=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; } for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ for(int k=1;k<=K;k++){ if(i==j) continue; if(B[i][k]>0&&S[j][k]>0) Q[i][j] = max(Q[i][j],S[j][k]-B[i][k]); } } } 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 74 ms | 2168 KB | Output is correct |
2 | Correct | 47 ms | 1408 KB | Output is correct |
3 | Correct | 34 ms | 1280 KB | Output is correct |
4 | Incorrect | 9 ms | 896 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 896 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 1524 KB | Output is correct |
2 | Correct | 125 ms | 2168 KB | Output is correct |
3 | Correct | 73 ms | 1528 KB | Output is correct |
4 | Correct | 43 ms | 1536 KB | Output is correct |
5 | Correct | 36 ms | 1536 KB | Output is correct |
6 | Correct | 84 ms | 1536 KB | Output is correct |
7 | Correct | 10 ms | 896 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 10 ms | 896 KB | Output is correct |
10 | Correct | 9 ms | 896 KB | Output is correct |
11 | Correct | 11 ms | 896 KB | Output is correct |
12 | Correct | 9 ms | 896 KB | Output is correct |
13 | Correct | 6 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 896 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |