oj.uz

Submission #631698

# Submission time Handle Problem Language Result Execution time Memory
631698 2022-08-18T13:19:44 Z CongHao Travelling Merchant (APIO17_merchant) C++14
0 / 100
 103 ms 2152 KB 
#include<bits/stdc++.h>
using namespace std;

#define db(val) "["#val" = "<<(val)<<"] "
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FOD(i,l,r) for(int i=(l);i>=(r);i--)
#define REP(i,l,r) for(int i=(l);i<(r);i++)

using ll=long long;

template<class T> void MAX(T &x,T y){if(x<y)x=y;}
template<class T> void MIN(T &x,T y){if(x>y)x=y;}

const ll inf=1e18;

const int N=105,K=1005;
ll xet[N][N],d[N][N],c[N][N];
ll b[N][K],s[N][K];
int n,m,k;

bool ok(ll f){
   FOR(i,1,n)FOR(j,1,n)
      xet[i][j]=1ll*f*min(inf/f,d[i][j])-c[i][j];
   FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)
      MIN(xet[i][j],xet[i][k]+xet[k][j]);
   FOR(i,1,n)if(xet[i][i]<=0)return 1;
   return 0;
}

void solve(){
   cin>>n>>m>>k;
   FOR(i,1,n)FOR(j,1,k)
      cin>>b[i][j]>>s[i][j];
   FOR(i,1,n)FOR(j,1,n)d[i][j]=inf;
   FOR(i,1,m){
      int x,y,t;cin>>x>>y>>t;
      d[x][y]=t;
   }
   FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)
      MIN(d[i][j],d[i][k]+d[k][j]);
   FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)
      if(s[j][k]!=-1&&b[i][k]!=-1)
         MAX(c[i][j],s[j][k]-b[i][k]);
   ll l=1,r=1e9,ans=0;
   while(l<=r){
      ll mid=(l+r)/2;
      if(ok(mid)){
         ans=mid;
         l=mid+1;
      }else r=mid-1;
   }
//   assert(ans!=-1);
   cout<<ans;
}

int32_t main(){
   cin.tie(0)->ios::sync_with_stdio(0);

   if(fopen("input.txt","r")){
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
      freopen(".log","w",stderr);
   }

   int tt=1;
//   cin>>tt;
   while(tt--){
      solve();
      cout<<'\n';
   }

   return 0;
}

Compilation message

merchant.cpp: In function 'int32_t main()':
merchant.cpp:60:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |       freopen("input.txt","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:61:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |       freopen("output.txt","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:62:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |       freopen(".log","w",stderr);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 2056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 7 ms 868 KB Output is correct
3 Correct 7 ms 836 KB Output is correct
4 Incorrect 5 ms 856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1492 KB Output is correct
2 Incorrect 103 ms 2152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 7 ms 868 KB Output is correct
3 Correct 7 ms 836 KB Output is correct
4 Incorrect 5 ms 856 KB Output isn't correct
5 Halted 0 ms 0 KB -