Submission #1139337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139337		eggx50000	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	492 ms	2496 KiB

merchant

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <assert.h>
using namespace std;
using ld = long double;
using ll = long long;
const ll mod = 1000000007;

int n, m, c;
ll brr[109][1099], srr[109][1099], dst[109][109], vve[109][109];
ld pee[109][109];

int main()
{
    scanf("%d %d %d", &n, &m, &c);
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= c; j ++) scanf("%lld %lld", brr[i] + j, srr[i] + j);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(i != j) dst[i][j] = 1000000000;
        }
    }
    for(int i = 1; i <= m; i ++){
        int a, b;
        ll c;
        scanf("%d %d %lld", &a, &b, &c);
        dst[a][b] = c;
    }
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                dst[i][j] = min(dst[i][j], dst[i][k] + dst[k][j]);
            }
        }
    }
    for(int k = 1; k <= c; k ++){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                if(brr[i][k] >= 0 && srr[j][k] >= 0) vve[i][j] = max(vve[i][j], srr[j][k] - brr[i][k]);
            }
        }
    }

    ld s = 0, e = 2e9;
    int t = 100;
    while(t --){
        ld m = (s + e)  / 2;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                if(i == j) pee[i][j] = -1e15;
                else pee[i][j] = vve[i][j] - m * dst[i][j];
            }
        }
        for(int k = 1; k <= n; k ++){
            for(int i = 1; i <= n; i ++){
                for(int j = 1; j <= n; j ++){
                    pee[i][j] = max(pee[i][j], pee[i][k] + pee[k][j]);
                }
            }
        }
        bool fl = false;
        for(int i = 1; i <= n; i ++){
            if(pee[i][i] >= 0) fl = true;
        }
        if(fl) s = m;
        else e = m;
    }
    printf("%lld", (ll)(e + 0.000000000000001));
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d %d %d", &n, &m, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:18:68: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     for(int i = 1; i <= n; i ++) for(int j = 1; j <= c; j ++) scanf("%lld %lld", brr[i] + j, srr[i] + j);
      |                                                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d %d %lld", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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