Submission #748670

#	Time	Username	Problem	Language	Result	Execution time	Memory
748670		snpmrnhlol	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	87 ms	4252 KiB

merchant

#include <iostream>
using namespace std;
typedef long long ll;
const ll N = 1e2,K = 1e3;
const ll inf = 1e9;
ll b[N][K],s[N][K],d[N][N];
ll p[N][N],p2[N][N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m,k,i,j,u,w,x,l;
    cin>>n>>m>>k;
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++)d[i][j] = inf;
        for(j = 0;j < k;j++){
            cin>>b[i][j]>>s[i][j];
        }
    }
    for(i = 0;i < m;i++){
        cin>>u>>w>>x;w--;u--;
        d[u][w] = x;
    }
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            for(l = 0;l < n;l++){
                d[j][l] = min(d[j][l],d[j][i] + d[i][l]);
            }
        }
    }
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            for(l=  0;l < k;l++){
                if(b[i][l] == -1 || s[j][l] == -1)continue;
                p2[i][j] = max(p2[i][j],s[j][l] - b[i][l]);
            }
        }
    }
    ll lef = 0,r = inf;
    while(lef != r){
        ll mij = (lef + r + 1)/2;
        for(i = 0;i < n;i++){
            for(j = 0;j < n;j++){
                p[i][j] = -d[i][j]*mij + p2[i][j];
            }
        }
        for(i = 0;i < n;i++){
            for(j = 0;j < n;j++){
                for(l = 0;l < n;l++){
                    p[j][l] = max(p[j][l],p[j][i] + p[i][l]);
                }
            }
        }
        bool ok = 0;
        for(i = 0;i < n;i++)if(p[i][i] >= 0){
            ok = 1;
        }
        if(ok)lef = mij;
        else r = mij - 1;
    }
    cout<<lef;
    return 0;
}

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