Submission #551466

#	Time	Username	Problem	Language	Result	Execution time	Memory
551466		Ai7081	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	91 ms	2120 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define long long long

const int N = 105;
const int I = 1005;
const long inf = 1e18;

long n, m, item, x, y, z, dis[N][N], fin[N][N], val[N][N], b[N][I], s[N][I];

int main() {
    scanf(" %lld %lld %lld", &n, &m, &item);
    for (int i=1; i<=n; i++) for (int j=1; j<=item; j++) scanf(" %lld %lld", &b[i][j], &s[i][j]);
    fill_n(dis[0], N*N, inf);
    while (m--) {
        scanf(" %lld %lld %lld", &x, &y, &z);
        dis[x][y] = z;
    }
    for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=item; k++) {
        if (b[i][k]!=-1  && s[j][k]!=-1) val[i][j] = max(val[i][j], s[j][k] - b[i][k]);
    }
//    for (int i=1; i<=n; i++) {for (int j=1; j<=n; j++) printf("%lld " , dis[i][j]); printf("\n");}
//    for (int i=1; i<=n; i++) {for (int j=1; j<=n; j++) printf("%lld " , val[i][j]); printf("\n");}
    long l=1, r=1e9;
    while (l <= r) {
        long mid = (l+r)>>1;
//        printf("%lld %lld %lld\n", l, mid, r);
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) fin[i][j] = mid * min(dis[i][j], inf/mid) - val[i][j];
        for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
            fin[i][j] = min(fin[i][j], fin[i][k] + fin[k][j]);
        }
        bool ok = false;
        for (int i=1; i<=n; i++) if (fin[i][i] <= 0) {ok=true; break;}
        if (ok) l = mid+1;
        else r = mid-1;
    }
    printf("%lld", r);
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf(" %lld %lld %lld", &n, &m, &item);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:13:63: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for (int i=1; i<=n; i++) for (int j=1; j<=item; j++) scanf(" %lld %lld", &b[i][j], &s[i][j]);
      |                                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf(" %lld %lld %lld", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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