Submission #110565

#	Time	Username	Problem	Language	Result	Execution time	Memory
110565		tictaccat	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	80 ms	3312 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;
const int MAX_N = 100;
const int MAX_K = 1000;

int N,M,K;
vector<vector<int>> adj(MAX_N,vector<int>(MAX_N,INF));
vector<vector<int>> B(MAX_N, vector<int>(MAX_K)), S(MAX_N, vector<int>(MAX_K));

main() {

    cin >> N >> M >> K;

    for (int i = 0; i < N; i++) {
        for (int z = 0; z < K; z++) {
            cin >> B[i][z] >> S[i][z];
        }
    }    

    for (int i = 0; i < M; i++) {
        int V,W,P; cin >> V >> W >> P;
        adj[V-1][W-1] = P;
    }

    auto dist = adj;

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int ans = 0;

    for (int i = 1; i < N; i++) {
        int val = 0;
        for (int z = 0; z < K; z++) {
            val = max(val,S[i][z] - B[0][z]);
        }
        ans = max(ans,val/(dist[0][i]+dist[i][0]));
    }

    cout << ans << "\n";


    return 0;
}

Compilation message (stderr)

merchant.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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