Submission #907640

#	Time	Username	Problem	Language	Result	Execution time	Memory
907640		vjudge1	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	49 ms	1876 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll 
#define ii pair<int,int>

const int N = 105;
const int K = 1010;

int buy[N][K];
int sell[N][K];

int n, m, k;

vector<ii> adj[N];

int dis[N][N];

signed main(){
    cin >> n >> m >> k;
    for(int i=0; i<n; ++i){
        for(int j=0; j<k; ++j){
            cin >> buy[i][j] >> sell[i][j];
        }
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            dis[i][j] = 4e18;
        }
    }
    for(int i=0; i<m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].push_back({v, w});
        dis[u][v] = min(dis[u][v], w);
    }

    // floyd
    for(int p=0; p<n; ++p){
        for(int u=0; u<n; ++u){
            for(int v=0; v<n; ++v){
                dis[u][v] = min(dis[u][v], dis[u][p] + dis[p][v]);
            }
        }
    }

    int ans = 0;
    for(int i=0; i<k; ++i){
        // suppose I'm buying the ith item
        if(buy[0][i] == -1) continue;
        for(int p=0; p<n; ++p){
            if(sell[p][i] == -1) continue;
            // I sell it in market p
            int profit = sell[p][i] - buy[0][i];
            profit /= dis[0][p] + dis[p][0];
            ans = max(ans, profit);
        }

    }
    cout << ans << endl;

}

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