Submission #1112269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112269		Zero_OP	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	85 ms	3400 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 4;
const long long infll = 1e18;

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) return a = b, true;
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M, K;
    cin >> N >> M >> K;

    vector<vector<array<int, 2>>> items(N, vector<array<int, 2>>(K)); //[buy, sell]
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < K; ++j){
            cin >> items[i][j][0] >> items[i][j][1];
        }
    }

    vector<vector<int>> dist(N, vector<int>(N, inf));

    while(M--){
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        dist[u][v] = w;
    }

    for(int k = 0; k < N; ++k){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                minimize(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    vector<vector<long long>> delta(N, vector<long long>(N, -infll));

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j) if(dist[i][j] != inf){
            for(int k = 0; k < K; ++k) if(items[i][k][0] != -1 && items[j][k][1] != -1){
                maximize(delta[i][j], - (long long)items[i][k][0] + items[j][k][1]);
            }
        }
    }

    vector<vector<long long>> f(N, vector<long long>(N, -infll));
    auto check = [&](int x){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                f[i][j] = max(0ll, delta[i][j]) - 1LL * x * dist[i][j];
            }
        }

        for(int k = 0; k < N; ++k){
            for(int i = 0; i < N; ++i){
                for(int j = 0; j < N; ++j){
                    maximize(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }

        for(int i = 0; i < N; ++i)
            if(f[i][i] >= 0) return true;
        return false;
    };

    int l = 0, r = 1e9, ans = 0;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

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

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