Submission #774472

#	Time	Username	Problem	Language	Result	Execution time	Memory
774472		MohamedFaresNebili	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	75 ms	4184 KiB

merchant

#include <bits/stdc++.h>

		using namespace std;
		using ll = long long;

		#define int ll

		int N, M, K;
		int S[101][1001], B[101][1001];
		int D[101][101], G[101][101];
		int DP[101][101];

		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 = 0; l < M; l++) {
                int V, W, T; cin >> V >> W >> T;
                D[V][W] = T;
            }

            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)
                            G[l][i] = max(G[l][i], S[i][j] - B[l][j]);
            for(int l = 1; l <= N; l++)
                for(int i = 1; i <= N; i++)
                    for(int j = 1; j <= N; j++)
                        D[i][j] = min(D[i][j], D[i][l] + D[l][j]);

            int lo = 1, hi = 1e9 + 7, res = 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] - G[l][i];

                for(int l = 1; l <= N; l++)
                    for(int i = 1; i <= N; i++)
                        for(int j = 1; j <= N; j++)
                            DP[i][j] = min(DP[i][j], DP[i][l] + DP[l][j]);

                bool can = false;
                for(int l = 1; l <= N; l++)
                    can |= (DP[l][l] <= 0);
                if(can) res = md, lo = md + 1;
                else hi = md - 1;
            }
            cout << res << "\n";
            return 0;
		}

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