Submission #745119

#	Time	Username	Problem	Language	Result	Execution time	Memory
745119		Trunkty	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	22 ms	2244 KiB

merchant

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

int n,m,k;
int store[105][1005][2];
int dist[105][105],prof[105][105];
int best[105][105][2];

signed main(){
    ios::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 >> store[i][j][0] >> store[i][j][1];
            if(store[i][j][0]==-1){
                store[i][j][0] = 2e9;
            }
            if(store[i][j][1]==-1){
                store[i][j][1] = -1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                dist[i][j] = 2e18;
            }
        }
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        dist[a][b] = c;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            prof[i][j] = -2e9;
            for(int k=1;k<=n;k++){
                prof[i][j] = max(prof[i][j],store[j][k][1]-store[i][k][0]);
            }
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << prof[i][j] << " ";
        }
        cout << "\n";
    }
    */
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                best[i][j][0] = prof[i][j];
                best[i][j][1] = dist[i][j];
            }
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(best[i][j][1]==0){
                        best[i][j][0] = best[i][k][0]+best[k][j][0];
                        best[i][j][1] = best[i][k][1]+best[k][j][1];
                    }
                    else{
                        if(best[i][k][1]+best[k][j][1]==0){
                            continue;
                        }
                        long double a = best[i][k][0]+best[k][j][0], b = best[i][k][1]+best[k][j][1], c = best[i][j][0], d = best[i][j][1];

                        if(a/b>c/d){
                            best[i][j][0] = a;
                            best[i][j][1] = b;
                        }
                    }
                }
            }
        }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(best[i][i][1]){
        ans = max(ans,best[i][i][0]/best[i][i][1]);
        }
    }
    cout << ans << "\n";
    return 0;
}

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