Submission #369450

#	Time	Username	Problem	Language	Result	Execution time	Memory
369450		Vladth11	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	161 ms	4352 KiB

merchant

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include "shoes.h"
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 101;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 35;
const long double eps = 0.0000000000000001;
 
double d[NMAX];
 
struct Edges {
    ll a, b;
    ll c;
};
 
ll dp[NMAX][NMAX];
ll dist[NMAX][NMAX];
ll profit[NMAX][NMAX];
ll n, m, k;
ll b[NMAX][1001], s[NMAX][1001];
 
bool OK(ll r) {
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++) {
            if(i == j){
                dp[i][j] = INF;
                continue;
            }
			if(dist[i][j] == INF){
              dp[i][j] = INF;
                continue;
			}
            dp[i][j] = r * dist[i][j] - profit[i][j];
        }
    }
    ll ok = 1;
    for(ll t = 1; t <= n; t++) {
        for(ll i = 1; i <= n; i++) {
            for(ll j = 1; j <= n; j++) {
                if(dp[i][t] == INF || dp[t][j] == INF)
                continue;
                dp[i][j] = min(dp[i][j], dp[i][t] + dp[t][j]);
            }
        }
    }
   for(ll i = 1; i <= n; i++){
        if(dp[i][i] <= 0)
            return 1;
   }
    return 0;
}
 
int main() {
    ll i;
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++) {
        for(ll j = 1; j <= k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++) {
            ll maxim = 0;
            dist[i][j] = INF;
            for(ll t = 1; t <= k; t++) {
                if(s[j][t] != -1 && b[i][t] != -1)
                maxim = max(maxim, s[j][t] - b[i][t]);
            }
            profit[i][j] = maxim;
        }
    }
    for(i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = c;
    }
    for(ll t = 1; t <= n; t++) {
        for(i = 1; i <= n; i++) {
            for(ll j = 1; j <= n; j++) {
                if(dist[i][t] == INF || dist[t][j] == INF)
                continue;
                dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
            }
        }
    }
    ll r = 0, pas = (1LL << 30);
    while(pas){
        if(OK(r + pas))
        r += pas;
        pas /= 2;
    }
    cout << r;
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'bool OK(ll)':
merchant.cpp:49:8: warning: unused variable 'ok' [-Wunused-variable]
   49 |     ll ok = 1;
      |        ^~

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