Submission #1162795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162795		Hamed_Ghaffari	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	44 ms	1352 KiB

merchant

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

using ll = long long;

#define mins(a,b) (a=min(a,b))
#define maxs(a,b) (a=max(a,b))

const int MXN = 100;
const ll  INF = 1e18;

int n;
void floyd(ll d[MXN][MXN]){
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                mins(d[i][j], d[i][k]+d[k][j]);
}

int s[MXN][MXN*10], b[MXN][MXN*10];
ll dis[MXN][MXN], cash[MXN][MXN], dp[MXN][MXN];

bool chk(int x) {
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            dp[i][j] = x * min(dis[i][j], INF/x) - cash[i][j];
    floyd(dp);
    for(int i=0; i<n; i++)
        if(dp[i][i]<=0)
            return 1;
    return 0;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int m, k;
    cin >> n >> m >> k;
    for(int i=0; i<n; i++) {
        fill(dis[i], dis[i]+n, INF);
        for(int j=0; j<k; j++) cin >> b[i][j] >> s[i][j];
    }
    for(int i=0, u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        dis[u-1][v-1] = w;
    }
    floyd(dis);
    for(int x=0; x<k; x++)
        for(int i=0; i<n; i++)
            if(b[i][x]!=-1)
                for(int j=0; j<n; j++)
                    if(s[j][x]!=-1)
                        maxs(cash[i][j], 1ll*s[j][x] - b[i][x]);
    int l=0, r=1e9+1;
    while(r-l>1)
        (chk(l+r>>1) ? l : r) = l+r>>1;
    cout << l << '\n';
    return 0;
}

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