Submission #978705

#	Time	Username	Problem	Language	Result	Execution time	Memory
978705		nnin	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	21 ms	3420 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define pli pair<ll,int>
#define ll long long

int N, M, K;
ll B[105][1005], S[105][1005], mindis[105][105], profit[105][105];
double ans[105][105];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>N>>M>>K;
    for(int i=1;i<=N;i++) for(int j=1;j<=K;j++) cin>>B[i][j]>>S[i][j];
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) mindis[i][j] = 1e18;
        mindis[i][i] = 0;
    }
    while(M--) {
        int u, v; ll w;
        cin>>u>>v>>w;
        mindis[u][v] = min(mindis[u][v], w);
    }
    for(int k=1;k<=N;k++) for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
        mindis[i][j] = min(mindis[i][j], mindis[i][k]+mindis[k][j]);
    }
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
        for(int k=1;k<=K;k++) {
            if(B[i][k]==-1 || S[j][k]==-1) continue;
            profit[i][j] = max(profit[i][j], S[j][k]-B[i][k]);
        }
        ans[i][j] = max(ans[i][j], (double)profit[i][j]/(double)mindis[i][j]);
    }
    for(int k=1;k<=N;k++) for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
        ans[i][j] = max(ans[i][j], (double)(profit[i][k]+profit[k][j])/(double)(mindis[i][k]+mindis[k][j]));
    }
    double mx = 0;
    for(int i=1;i<=N;i++) mx = max(mx, ans[i][i]);
    ll answer = mx+0.5;
    cout<<answer;
}

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