Submission #674907

#	Time	Username	Problem	Language	Result	Execution time	Memory
674907		Cookie	Travelling Merchant (APIO17_merchant)	C++14	33 / 100	85 ms	2072 KiB

merchant

#include<bits/stdc++.h>

using namespace std;
#include<fstream>

#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll mod=  1e9 + 7;
const int mxk = 1e3, sq = 750, mxn = 105;
ll best[mxn + 1][mxn + 1], d[mxn + 1][mxn + 1], s[mxn + 1][mxk + 1], b[mxn + 1][mxk + 1];
int n, m, k;
struct e{
    ll u, v, w;
};
vt<e>edge;
bool ck(ll mid){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            d[i][j] = 1e18;
        }
    }
    for(auto [u, v, w]: edge){
        d[u][v] = min(d[u][v], w * mid - best[u][v]);
       // cout << u << ' ' << v << " " << w * mid - best[u][v] << "\n";
    }   
    for(int l = 1; l <= n; l++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(d[i][l] != 1e18 && d[l][j] != 1e18){
                    d[i][j] = min(d[i][j], d[i][l] + d[l][j]);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(d[i][i] <= 0)return(true);
    }
    return(false);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    forr(i, 0, m){
        int u, v, w; cin >> u >> v >> w;
        edge.pb({u, v, w});
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j)continue;
            for(int l = 1; l <= k; l++){
                if(s[j][l] == -1 || b[i][l] == -1)continue;
                best[i][j] = max(best[i][j], s[j][l] - b[i][l]);
            }
        }
    }
    ll l = 1, r = 1e9, ans = 0;
    while(l <= r){
        ll mid = l + (r - l) / 2;
        if(ck(mid)){
            ans = mid; l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans;
    return(0);
}

Compilation message (stderr)

merchant.cpp: In function 'bool ck(long long int)':
merchant.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [u, v, w]: edge){
      |              ^

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