제출 #545864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545864		Monarchuwu	여행하는 상인 (APIO17_merchant)	C++17	33 / 100	75 ms	3164 KiB

merchant

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
using namespace std;

const int N = 100 + 2, M = 9900 + 4, K = 1000 + 3, inf = 1e9 + 7;
const ll inf2 = 2e18;
int n, m, k;
int b[N][K], s[N][K], t[N][N];

ll dist[N][N];
void maxi(ll &a, ll b) { if (a < b) a = b; }
bool check(ll x) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = -inf2;
            if (!t[i][j]) continue;

            for (int kk = 0; kk < k; ++kk) {
                if (!~b[i][kk] || !~s[j][kk]) continue;
                maxi(dist[i][j], max(0, s[j][kk] - b[i][kk]) - t[i][j] * x);
            }
        }

    for (int kk = 1; kk <= n; ++kk)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                maxi(dist[i][j], dist[i][kk] + dist[kk][j]);

    for (int i = 1; i <= n; ++i)
        if (dist[i][i] >= 0) return true;
    return false;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < k + k; ++j) {
            if (j & 1)
                cin >> s[i][j >> 1];
            else cin >> b[i][j >> 1];
        }
    }
    for (int i = 0, a, b; i < m; ++i) {
        cin >> a >> b;
        cin >> t[a][b];
    }

    int lo(0), hi(inf), mid;
    while (lo <= hi) {
        mid = (lo + hi) >> 1;
        if (check(mid))
            lo = mid + 1;
        else hi = mid - 1;
    }
    cout << lo - 1 << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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