Submission #1158356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158356		Sang	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	54 ms	2236 KiB

merchant

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

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, m, k, b[105][1005], s[105][1005], profit[105][105], dist[105][105], d[105][105];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n >> m >> k;
    FOR (i, 1, n){
        FOR (j, 1, k) cin >> b[i][j] >> s[i][j];
    }
    FOR (i, 1, n) FOR (j, 1, n) dist[i][j] = 1e18;
    FOR (i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
    }
    FOR (i, 1, n){
        FOR (j, 1, n){
            FOR (z, 1, k){
                if (b[i][z] == -1 || s[j][z] == -1) continue;
                profit[i][j] = max(profit[i][j], s[j][z] - b[i][z]);
            }
        }
    }
    FOR (k, 1, n) FOR (i, 1, n) FOR (j, 1, n){
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    int l = 1, r = 1e9, ans = 0;
    while (l <= r){
        int m = (l + r)/2;
        FOR (i, 1, n) FOR (j, 1, n){
            if (dist[i][j] == 1e18){
                d[i][j] = -1e18;
            } else d[i][j] =  profit[i][j] -  m * dist[i][j];
        }
        FOR (k, 1, n) FOR (i, 1, n) FOR (j, 1, n) d[i][j] = max(d[i][j], d[i][k] + d[k][j]);
        bool ok = 0;
        FOR (i, 1, n) ok |= (d[i][i] >= 0);
        if (ok){
            ans = m;
            l = m + 1;
        } else r = m - 1;
    }
    cout << ans;




    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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