Submission #551469

#	Time	Username	Problem	Language	Result	Execution time	Memory
551469		Ai7081	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	33 ms	2004 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define long long long
const bool debug = 0;

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

struct item{
    long x, t;
    item() : t(inf) {}
    item(long x, long t) : x(x), t(t) {}
    bool operator < (const item &o) const {
        if (!t) return true;
        if (!o.t) return false;
        if (x == 0 && o.x == 0) return t < o.t;
        return x*o.t < t*o.x;
    }
    bool operator > (const item &o) const {return !(*this < o);}
    item operator + (const item &o) {return item(x+o.x, t+o.t);}
    void operator += (const item &o) {x+=o.x; t+=o.t;}
};

long n, m, k, b[N][K], s[N][K];
item dis[N][N], out;

int main() {
    scanf(" %lld %lld %lld", &n, &m, &k);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=k; j++) scanf(" %lld %lld", &b[i][j], &s[i][j]);
    }
    while (m--) {
        long x, y, z;
        scanf(" %lld %lld %lld", &x, &y, &z);
        dis[x][y].t = z;
    }
    for (int i=1; i<=n; i++) dis[i][i].t = 0;
    for (int c=1; c<=n; c++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
        dis[i][j].t = min(dis[i][j].t, dis[i][c].t+dis[c][j].t);
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
        if (dis[i][j].t != inf) {
            for (int c=1; c<=k; c++) if (b[i][c]!=-1 && s[j][c]!=-1) {
                dis[i][j].x = max(dis[i][j].x, s[j][c]-b[i][c]);
            }
        }
    }

    if (debug) {
        for (int i=1; i<=n; i++) {
            printf("dis %d : ", i);
            for (int j=1; j<=n; j++) printf("(%lld %lld) ", dis[i][j].x, dis[i][j].t);
            printf("\n");
        }
    }

    for (int c=1; c<=n; c++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) if (dis[i][c].t && dis[c][j].t) {
                dis[i][j] = max(dis[i][j], dis[i][c] + dis[c][j]);
            }
        }
    }

    for (int i=1; i<=n; i++) out = max(out, dis[i][i]);
    if (debug) printf("%lld %lld\n", out.x, out.t);
    printf("%lld", out.t ? out.x/out.t : 0);
    return 0;
}

/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

5 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
-1 -1 -1 -1
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

Compilation message (stderr)

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

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