Submission #899229

#	Time	Username	Problem	Language	Result	Execution time	Memory
899229		AdamGS	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	103 ms	4432 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=107;
const ll INF=1e18+7;
ll kraw[LIM][LIM], B[LIM][10*LIM], S[LIM][10*LIM], n, k;
ll zysk[LIM][LIM], odl[LIM][LIM], tmp[LIM][LIM];
ll dist[LIM], wrz;
void poteguj() {
  rep(i, 20) {
    rep(i, n) rep(j, n) {
      tmp[i][j]=odl[i][j];
      rep(l, n) if(odl[i][l]!=-INF && odl[l][j]!=-INF) {
        tmp[i][j]=max(tmp[i][j], min(INF, odl[i][l]+odl[l][j]));
      }
    }
    rep(i, n) rep(j, n) odl[i][j]=tmp[i][j];
  }
}
bool cykl(ll x) {
  rep(i, n) dist[i]=-INF;
  dist[x]=0;
  while(true) {
    ll ma=-INF, ind=-1;
    rep(i, n) if(dist[i]>ma && dist[i]<INF) {
      ma=dist[i];
      ind=i;
    }
    if(ind==-1) break;
    ll o=dist[ind]; dist[ind]=INF;
    if(o+odl[ind][x]>=0) return true;
    rep(i, n) {
      if(dist[i]<INF && dist[i]<o+odl[ind][i]) {
        dist[i]=o+odl[ind][i];
        dist[i]=min(dist[i], INF-1);
      }
    }
  }
  return false;
}
bool f(ll x) { 
  rep(i, n) rep(j, n) {
    if(kraw[i][j]==-INF) odl[i][j]=-INF;
    else {
      odl[i][j]=kraw[i][j]*x;
      if(zysk[i][j]>=0) odl[i][j]+=zysk[i][j];
    }
  }
  rep(i, n) rep(j, n) odl[i][j]*=-1;
  rep(k, n) rep(i, n) rep(j, n) if(odl[i][k]<INF && odl[k][j]<INF) {
    odl[i][j]=min(odl[i][j], odl[i][k]+odl[k][j]);
  }
  rep(i, n) if(odl[i][i]<=0) return true;
  return false;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int m;
  cin >> n >> m >> k;
  rep(i, n) rep(j, n) kraw[i][j]=-1;
  rep(i, n) rep(j, k) cin >> B[i][j] >> S[i][j];
  rep(i, m) {
    ll a, b, c;
    cin >> a >> b >> c; --a; --b;
    if(kraw[a][b]==-1) kraw[a][b]=c;
    kraw[a][b]=min(kraw[a][b], c);
  }
  rep(i, n) rep(j, n) {
    zysk[i][j]=-INF;
    rep(l, k) if(i!=j && B[i][l]!=-1 && S[j][l]!=-1) {
      zysk[i][j]=max(zysk[i][j], S[j][l]-B[i][l]);
    }
  }
  rep(i, n) rep(j, n) if(kraw[i][j]==-1) odl[i][j]=-INF; else odl[i][j]=-kraw[i][j];
  poteguj();
  rep(i, n) rep(j, n) kraw[i][j]=odl[i][j];
  ll po=0, ko=1000000000;
  while(po<ko) {
    ll sr=(po+ko+1)/2;
    if(f(sr)) po=sr; else ko=sr-1;
  }
  cout << po << '\n';
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34