Submission #1149474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149474		dosts	Travelling Merchant (APIO17_merchant)	C++20	12 / 100	73 ms	2112 KiB

merchant

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e14,N = 3e5+1,MOD = 998244353,BL = 1000;

void solve() { 
    int n,m,k;
    cin >> n >> m >> k;
    int b[n+1][k+1],s[n+1][k+1];
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=k;j++) {
            cin >> b[i][j] >> s[i][j];
            if (b[i][j] == -1) b[i][j] = inf;
            if (s[i][j] == -1) s[i][j] = -inf;
        }
    }
    int profit[n+1][n+1]{};
    for (int i=1;i<=n;i++) {
        for (int j = i+1;j<=n;j++) {
            for (int p = 1;p<=k;p++) {
                profit[i][j] = max(profit[i][j],s[j][p]-b[i][p]);
                profit[j][i] = max(profit[j][i],s[i][p]-b[j][p]);
            }
        } 
    }
    int d[n+1][n+1];
    for (int i=0;i<=n;i++) for (int j = 0;j<=n;j++) d[i][j] = inf;
    for (int i=1;i<=n;i++) d[i][i] = 0;
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b],c);
    }
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=n;j++) {
            for (int k = 1;k<=n;k++) {
                d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
                d[k][j] = min(d[k][j],d[k][i]+d[i][j]);
            }
        }
    }
    int go[n+1][n+1];
    pii lp[n+1],lp2[n+1];
    int l = 0;
    int r = 1e16;
    while (l<=r){
        int w = (l+r) >> 1;
        for (int i=1;i<=n;i++) {
            lp[i] = {0,0};
            for (int j = 1;j<=n;j++) {
                go[i][j] = max(-inf,profit[i][j]-w*d[i][j]);
            }
        }
        bool yes = 0;
        for (int ii=1;ii<=n;ii++) {
            for (int i=1;i<=n;i++) lp2[i] = lp[i];
            bool fl = 0;
            for (int i = 1;i<=n;i++) {
                for (int j = 1;j<=n;j++) {
                    if (i == j) continue;
                    if (lp[j].ff >= inf) continue;
                    if (pii{lp2[i].ff+go[i][j],lp2[i].ss+1} > lp[j]) {
                        lp[j] = {lp2[i].ff+go[i][j],lp2[i].ss+1};
                        fl = 1;
                    }
                }
            }
            if (ii == n && fl) {
                yes = 1;
            }
        }
        if (!yes) r = w-1;
        else l = w+1;
    }
    cout << r << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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