Submission #943196

#	Time	Username	Problem	Language	Result	Execution time	Memory
943196		adhityamv	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	115 ms	4296 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int INF=1000000000000000000;
void solve(){
    int n,m,l;
    cin >> n >> m >> l;
    int b[n][l];
    int s[n][l];
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    vector<pii> edges[n];
    int dist[n][n];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) dist[i][j]=INF;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u--,v--;
        dist[u][v]=w;
    }
    for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(dist[i][j]==INF) dist[i][j]=-1;
    int profit[n][n];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){
        profit[i][j]=0;
        for(int k=0;k<l;k++){
            if(b[i][k]<s[j][k] && b[i][k]!=-1 && s[j][k]!=-1) profit[i][j]=max(profit[i][j],s[j][k]-b[i][k]);
        }
    }
    //for(int i=0;i<n;i++) for(int j=0;j<n;j++) cout << dist[i][j] << "->" << i << "," << j << "\n";
    //cout << "\n\n\n";
    //for(int i=0;i<n;i++) for(int j=0;j<n;j++) cout << profit[i][j] << "->" << i << "," << j << "\n";
    int lft=0;
    int rgt=INF;
    while(lft<rgt){
        int mid=(lft+rgt+1)/2;
        int w[n][n];
        bool valid=false;
        for(int i=0;i<n;i++) for(int j=0;j<n;j++){
            if(dist[i][j]==-1) w[i][j]=INF;
            else if(dist[i][j]>(INF+profit[i][j])/mid) w[i][j]=INF;
            else w[i][j]=mid*dist[i][j]-profit[i][j];
        }
        //for(int i=0;i<n;i++) for(int j=0;j<n;j++) cout << w[i][j] << "->" << i << "," << j << "\n";
        for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
        for(int i=0;i<n;i++) if(w[i][i]<=0) valid=true;
        if(valid){
            lft=mid;
        } else rgt=mid-1;
    }
    cout << lft;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin >> t;
    while(t--) solve();
}

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