Submission #943182

#	Time	Username	Problem	Language	Result	Execution time	Memory
943182		adhityamv	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	73 ms	3420 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;
            if(dist[i][j]>(INF+profit[i][j])/mid) w[i][j]=INF;
            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(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:61:10: warning: variable 'begin' set but not used [-Wunused-but-set-variable]
   61 |     auto begin = std::chrono::high_resolution_clock::now();
      |          ^~~~~

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