Submission #270797

#	Time	Username	Problem	Language	Result	Execution time	Memory
270797		NaimSS	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	114 ms	4244 KiB

merchant

    #include <bits/stdc++.h>
    #define ld long double
    #define endl "\n"
    #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define pb(x) push_back(x)
    #define mp(a,b) make_pair(a,b)
    #define ms(v,x) memset(v,x,sizeof(v))
    #define all(v) v.begin(),v.end()
    #define ff first
    #define ss second
    #define rep(i, a, b) for(int i = a; i < (b); ++i)
    #define per(i, a, b) for(int i = b-1; i>=a ; i--)
    #define trav(a, x) for(auto& a : x)
    #define allin(a , x) for(auto a : x)
    #define td(v) v.begin(),v.end()
    #define sz(v) (int)v.size()
    //#define int long long
    using namespace std;
    typedef vector<int> vi;
    #define y1 abacaba
    #define left sefude
    #define db(x) cerr << #x <<" == "<<x << endl;
    #define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
    #define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; 
    typedef long long ll;
    typedef pair<ll,ll> pll;
    typedef pair<int,int> pii;
    inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
    ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
    ll exp(ll a,ll b,ll m){
        if(b==0LL) return 1LL;
        if(b==1LL) return mod(a,m);
        ll k = mod(exp(a,b/2,m),m);
        if(b&1LL){
            return mod(a*mod(k*k,m),m);
        }
        else return mod(k*k,m);
    }
     
    const int N = 105;
    const int K = 1010;
    ll S[N][K],B[N][K];
    const ll inf = 1e9 + 2;
    ll dist[N][N];
    ll dp[N][N];
    ll best[N][N];
    int n,m,k;
    const ll inf2 = 1e18;
    bool ok(ll x){
      
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          if(dist[i][j]!=inf2){
            dp[i][j] = dist[i][j] * x - best[i][j];
          }else dp[i][j] = inf2;
        }
      }
      for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
          }
        }
      }
      for(int i=1;i<=n;i++){
        if(dp[i][i]<=0)return 1;
      }
      return 0;
    }
     
    int32_t main(){
      fastio;
      cin >> n >> m >> k;
      for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
          cin >> B[i][j] >> S[i][j];
        }
      }
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          dist[i][j] = inf2;
          best[i][j] = 0;
          for(int s=1;s<=k;s++){
            if(B[i][s]!=-1 and S[j][s]!=-1){
              best[i][j] = max(best[i][j],S[j][s] - B[i][s]);
            }
          }
        }
      }
     
      for(int i=0;i<m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        dist[a][b] = c;
      }
      
      //dist[1][1] = inf;
      
      for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
          }
        }
      }
      
     
      int l = 0, r = 1e9;
      int ans = 0;
      
      while(l<=r){
        int mid = (l + r)/2;
        if(ok(mid)){
          ans = mid;
          l = mid + 1;
        }else r = mid - 1;
      }
     
      cout << ans << endl;
     
      // math -> gcd it all
      // Did u check N=1? Did you switch N,M?
    }

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