Submission #627330

#	Time	Username	Problem	Language	Result	Execution time	Memory
627330		MohamedFaresNebili	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	98 ms	4212 KiB

merchant

#include <bits/stdc++.h>

            using namespace std;

            using ll = long long;
            using ld = long double;
            using pi = pair<pair<int, int>, pair<int, int>>;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
            #define int ll

            int N, M, K, B[105][1005], S[105][1005];
            int D[105][105], P[105][105], DP[105][105];

            void solve(int A[105][105]) {
                for(int l = 1; l <= N; l++)
                    for(int i = 1; i <= N; i++)
                        for(int j = 1; j <= N; j++)
                            A[i][j] = min(A[i][j], A[i][l] + A[l][j]);
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M >> K;
                for(int l = 1; l <= N; l++)
                    for(int i = 1; i <= N; i++)
                        D[l][i] = 1e9 + 7;
                for(int l = 1; l <= N; l++) {
                    for(int i = 1; i <= K; i++) {
                        cin >> B[l][i] >> S[l][i];
                    }
                }
                for(int l = 1; l <= M; l++) {
                    int U, V, C; cin >> U >> V >> C;
                    D[U][V] = C;
                }
                for(int l = 1; l <= N; l++) {
                    for(int i = 1; i <= N; i++) {
                        for(int j = 1; j <= K; j++) {
                            if(B[l][j] == -1 || S[i][j] == -1) continue;
                            P[l][i] = max(P[l][i], S[i][j] - B[l][j]);
                        }
                    }
                }
                solve(D);
                int lo = 1, hi = 1e9 + 7, ans = 0;
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    for(int l = 1; l <= N; l++)
                        for(int i = 1; i <= N; i++)
                            DP[l][i] = md * D[l][i] - P[l][i];
                    solve(DP); bool ok = 0;
                    for(int l = 1; l <= N; l++)
                        ok |= (DP[l][l] <= 0);
                    if(ok) ans = md, lo = md + 1;
                    else hi = md - 1;
                }
                cout << ans << "\n";
                return 0;
            }

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