Submission #923845

#	Time	Username	Problem	Language	Result	Execution time	Memory
923845		irmuun	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	125 ms	4248 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=100,inf=1e18;

ll n,m,k;
ll dist[N][N],profit[N][N],adj[N][N],adj2[N][N];

bool check(ll x){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            if(dist[i][j]==inf){
                adj[i][j]=-inf;
            }
            else{
                adj[i][j]=max(profit[i][j]-dist[i][j]*x,-inf);
            }
        }
        adj[i][i]=-inf;
    }
    ll res=-inf;
    for(ll r=0;r<n;r++){
        for(ll i=0;i<n;i++){
            for(ll j=0;j<n;j++){
                adj[i][j]=max(adj[i][j],adj[i][r]+adj[r][j]);
                res=max(res,adj[i][i]);
                if(res>=0){
                    return true;
                }
                adj[i][j]=min(adj[i][j],inf);
                adj2[i][j]=adj[i][j];
            }
        }
    }
    for(ll r=0;r<n;r++){
        for(ll i=0;i<n;i++){
            for(ll j=0;j<n;j++){
                adj2[i][j]=max(adj2[i][j],adj2[i][r]+adj2[r][j]);
                if(adj2[i][j]>adj[i][j]){
                    return true;
                }
            }
        }
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    ll b[n][k],s[n][k];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++){
            cin>>b[i][j]>>s[i][j];
        }
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            dist[i][j]=inf;
        }
        dist[i][i]=0;
    }
    for(ll i=0;i<m;i++){
        ll u,v,t;
        cin>>u>>v>>t;
        u--,v--;
        dist[u][v]=t;
    }
    for(ll r=0;r<n;r++){
        for(ll i=0;i<n;i++){
            for(ll j=0;j<n;j++){
                dist[i][j]=min(dist[i][j],dist[i][r]+dist[r][j]);
            }
        }
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            profit[i][j]=0;
            for(ll c=0;c<k;c++){
                if(s[j][c]>-1&&b[i][c]>-1){
                    profit[i][j]=max(profit[i][j],s[j][c]-b[i][c]);
                }
            }
        }
    }
    ll l=0,r=1e9+1;
    while(l<r){
        ll mid=(l+r+1)/2;
        if(check(mid)==true){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }
    cout<<l;
}

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