Submission #1160448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160448		AlgorithmWarrior	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	118 ms	2252 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=105;
int n,m,prod;
long long buy[MAX][1005];
long long sell[MAX][1005];
long long path[MAX][MAX];
long long profit[MAX][MAX];

void read(){
    cin>>n>>m>>prod;
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=prod;++j)
            cin>>buy[i][j]>>sell[i][j];
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            path[i][j]=INF;
    for(i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        path[u][v]=w;
    }
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

void roy_floyd(long long mat[][MAX]){
    int i,j,k;
    for(k=1;k<=n;++k)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                minself(mat[i][j],mat[i][k]+mat[k][j]);
}

void get_profit(){
    int i,j,k;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j){
            for(k=1;k<=prod;++k)
                if(buy[i][k]!=-1 && sell[j][k]!=-1)
                    maxself(profit[i][j],sell[j][k]-buy[i][k]);
        }
}

long long way[MAX][MAX];

bool check(int rasp){
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(path[i][j]<INF)
                way[i][j]=path[i][j]*rasp-profit[i][j];
            else
                way[i][j]=INF;
    roy_floyd(way);
    for(i=1;i<=n;++i)
        if(way[i][i]<=0)
            return 1;
    return 0;
}

int bin_search(){
    /// [)
    int st=0,dr=1e9;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij))
            st=mij;
        else
            dr=mij;
    }
    return st;
}

int main()
{
    read();
    roy_floyd(path);
    get_profit();
    cout<<bin_search();
    return 0;
}

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