Submission #484762

#	Time	Username	Problem	Language	Result	Execution time	Memory
484762		sam571128	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	88 ms	5316 KiB

merchant

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e3+5;
int dis[N][N], profit[N][N], b[N][N], s[N][N], dis2[N][N];
int n,m,k;

bool check(int x){
    assert(x!=0);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            dis2[i][j] = x*min(dis[i][j],(int)1e18/x) - profit[i][j];
        }
    }

    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                dis2[i][j] = min(dis2[i][j],dis2[i][k]+dis2[k][j]);
            }
        }
    }

    for(int i = 1;i <= n;i++) if(dis2[i][i] <= 0) return true;
    return false;
}

signed main(){
    fastio
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1;j <= n;j++){
            dis[i][j] = 1e18;
        }
        for(int j = 1;j <= k;j++){
            cin >> b[i][j] >> s[i][j];
            //Meaning that the cost to buy item j in market i 
        }
    }

    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        dis[u][v] = w;
    }

    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            for(int x = 1; x <= k; x++){
                if(s[j][x] == -1 || b[i][x] == -1) continue;
                profit[i][j] = max(profit[i][j],s[j][x]-b[i][x]);
            }
        }
    }

    int l = 1, r = 1e9;

    while(l+1 < r){
        //cout << l << " " << r << "\n";
        int mid = l+r>>1;
        if(!check(mid)) r = mid-1;
        else l = mid;
    }
    if(check(r)) cout << r << "\n";
    else if(check(l)) cout << l << "\n";
    else cout << 0 << "\n";
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:72:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l+r>>1;
      |                   ~^~

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