Submission #984314

#	Time	Username	Problem	Language	Result	Execution time	Memory
984314		Unforgettablepl	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	75 ms	4320 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

pair<int,int> dist[101][101];
int buy[101][1001];
int sell[101][1001];
int n;

bool check(int x){
    vector<vector<int>> adj(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        adj[i][j] = x*min(dist[i][j].first,INF/x) - dist[i][j].second;
    }
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
    }
    for(int i=1;i<=n;i++)if(adj[i][i]<=0)return true;
    return false;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,l;
    cin >> n >> m >> l;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j].first=INF;
//    for(int i=1;i<=n;i++)dist[i][i].first=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=l;j++)cin>>buy[i][j]>>sell[i][j];
    for(int i=1;i<=m;i++){
        int u,v,t;cin>>u>>v>>t;
        dist[u][v].first = t;
    }
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        dist[i][j].first = min(dist[i][j].first,dist[i][k].first+dist[k][j].first);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        for(int item=1;item<=l;item++){
            if(buy[i][item]==-1 or sell[j][item]==-1)continue;
            dist[i][j].second = max(dist[i][j].second,sell[j][item]-buy[i][item]);
        }
    }
    int ans = 0;
    for(int jump=1073741824ll;jump;jump/=2){
        if(check(ans+jump))ans+=jump;
    }
    cout << ans << '\n';
}

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