Submission #631698

#	Time	Username	Problem	Language	Result	Execution time	Memory
631698		CongHao	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	103 ms	2152 KiB

merchant

#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 (stderr)

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
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34