# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101991 | 2019-03-21T09:23:33 Z | bakpark | Travelling Merchant (APIO17_merchant) | C++14 | 147 ms | 2040 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 106 ms | 2040 KB | Output is correct |
2 | Correct | 42 ms | 1336 KB | Output is correct |
3 | Correct | 50 ms | 1280 KB | Output is correct |
4 | Incorrect | 8 ms | 768 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 1460 KB | Output is correct |
2 | Correct | 147 ms | 2040 KB | Output is correct |
3 | Correct | 43 ms | 1280 KB | Output is correct |
4 | Correct | 45 ms | 1528 KB | Output is correct |
5 | Correct | 56 ms | 1492 KB | Output is correct |
6 | Correct | 46 ms | 1280 KB | Output is correct |
7 | Correct | 13 ms | 768 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 10 ms | 888 KB | Output is correct |
10 | Correct | 10 ms | 896 KB | Output is correct |
11 | Correct | 8 ms | 768 KB | Output is correct |
12 | Correct | 8 ms | 768 KB | Output is correct |
13 | Correct | 7 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |